A note on adaptable choosability and choosability with separation of planar graphs
2021 (English)In: Journal of Combinatorial Mathematics and Combinatorial Computing, ISSN 0835-3026, Vol. 116, p. 101-109Article in journal (Refereed) Published
Abstract [en]
Let F be a (possibly improper) edge-coloring of a graph G; a vertex coloring of G is adapted to F if no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that given any list assignment L to the vertices of G, with |L(v)| ≥ k for all v, and any edge-coloring F of G, G admits a coloring c adapted to F where c(v) ∈ L(v) for all v, then G is said to be adaptably k-choosable. A (k, d)-list assignment for a graph G is a map that assigns to each vertex v a list L(v) of at least k colors such that |L(x) ∩ L(y)\ ≤ d whenever x and y are adjacent. A graph is (k, d)-choosable if for every (k, d)-list assignment L there is an L-coloring of G. It has been conjectured that planar graphs are (3, l)-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably 3-choosable. Since (k, l)-choosability is a special case of adaptable k-choosablity, this implies that a planar graph satisfying these conditions is (3,1)-choosable.
Place, publisher, year, edition, pages
Charles Babbage Research Centre , 2021. Vol. 116, p. 101-109
Keywords [en]
Coloring, Graphic methods, Choosability, Choosable, Edge coloring, Graph G, List assignment, Planar graph, Vertex coloring, Graph theory, Adaptable choosability, Choosability with separation, List coloring
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-188195Scopus ID: 2-s2.0-85112564602OAI: oai:DiVA.org:liu-188195DiVA, id: diva2:1693154
Note
Funding agencies:Carl Johan Casselgren was supported by a grant from the Swedish Research Council (2017-05077). André Raspaud was partially supported by the ANR project HOSIGRA (ANR- 17-CE40-0022)
2022-09-052022-09-052022-12-21