2-distance list (Δ+2)-coloring of planar graphs with girth at least 10
share
Given a graph G and a list assignment L(v) for each vertex of v of G. A proper L-list-coloring of G is a function that maps every vertex to a color in L(v) such that no pair of adjacent vertices have the same color. We say that a graph is list k-colorable when every vertex v has a list of colors of size at least k. A 2-distance coloring is a coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance list (Δ+2)-coloring for planar graphs with girth at least 10 and maximum degree Δ≥ 4.
READ FULL TEXT