VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • 5-list-coloring planar graphs with distant precolored vertices
    Dvořák, Zdeněk ...
    We answer positively the question of M. O. Albertson [M.O. Albertson, You can't paint yourself into a corner, J. Combin. Theory Ser. B 73(2) (1998) 189-194] asking whether every planar graph can be ... 5-list-colored even if it contains precolored vertices, as long as they are sufficiently far apart from each other. In order to prove this claim, we also give bounds on the sizes of graphs critical with respect to 5-list coloring. In particular, if ▫$G$▫ is a planar graph, ▫$H$▫ is a connected subgraph of ▫$G$▫ and ▫$L$▫ is an assignment of lists of colors to the vertices of ▫$G$▫ such that ▫$| L(v) | \geq 5$▫ for every ▫$v \in V(G) \setminus V(H)$▫ and ▫$G$▫ is not ▫$L$▫-colorable, then ▫$G$▫ contains a subgraph with ▫$O(| H |^2)$▫ vertices that is not ▫$L$▫-colorable.
    Vir: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 122, 2017, str. 311-352)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2017
    Jezik - angleški
    COBISS.SI-ID - 17882713

    Povezava(-e):

    http://dx.doi.org/10.1016/j.jctb.2016.06.006

Vnos na polico