2020/10/30 by Carl Johan Casselgren, Casselgren, Carl Johan, Jonas B. Granholm +3 · 1 citation
Computer Science · Social Sciences · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #French Urban and Social Studies #Graph Labeling and Dimension Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2010.16190
openalex publication_date 2020/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let F be a (possibly improper) edge-coloring of a graph G; a vertex\ncoloring of G is \adapted to F if no color appears at the same time\non an edge and on its two endpoints. If for some integer k, a graph G is\nsuch that given any list assignment L to the vertices of G, with |L(v)|\n\≥ k for all v, and any edge-coloring F of G, G admits a coloring c\nadapted to F where c(v) \∈ L(v) for all v, then G is said to be\n\adaptably k-choosable. A em (k,d)-list assignment for a graph G\nis a map that assigns to each vertex v a list L(v) of at least k colors\nsuch that |L(x) \∩ L(y)| \≤ d whenever x and y are adjacent. A graph\nis em (k,d)-choosable if for every (k,d)-list assignment L there is an\nL-coloring of G. It has been conjectured that planar graphs are\n(3,1)-choosable. We give some progress on this conjecture by giving\nsufficient conditions for a planar graph to be adaptably 3-choosable. Since\n(k,1)-choosability is a special case of adaptable k-choosablity, this\nimplies that a planar graph satisfying these conditions is (3,1)-choosable.\n