Journal of East China Normal University(Natural Sc

Previous Articles     Next Articles

3-hued coloring of planar graphs

QI Lin-ming[1], LI Jin-bo[2], LI Wei-qi[2]   

  1. 1. School of Tourism and Public Management, Huzhou Vocational and Technical College, Huzhou Zhejiang 313000, China;
    2. College of Sciences, China University of Mining and Technology, Xuzhou Jiangsu 221000, China
  • Received:2016-01-26 Online:2017-01-25 Published:2017-01-13


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