Abstract:

For a fixed integer k, r > 0, a (k, r)-coloring of a graph G is a proper k-coloring such that for any vertex v with degree d(v), the adjacent vertex of v is adjacent to at least min{d(v), r} different colors. Such coloring is also called as a r-hued coloring. The r-hued chromatic number of G, denoted by χr(G), is the smallest integer k such that G has a (k, r)-coloring. In this paper, we prove that if G is a planar graph, then χ3(G)≤12.

Key words: planar graphs, minimal counterexample, Lebesgue formula