(1, k)‐Coloring of Graphs with Girth at Least Five on a Surface. Issue 4 (10th March 2016)

• Record Type: Journal Article
• Authors: Choi, Hojin; Choi, Ilkyoo; Jeong, Jisu; Suh, Geewon
• Is Part Of: Journal of graph theory. Volume 84:Issue 4(2017)
• Page Start: 521
• Page End: 535
• Publication Date: 2016-03-10
• Subjects: improper coloring -- discharging -- graphs on surfaces; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22039
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A graph is ( d 1, ..., d r ) ‐colorable if its vertex set can be partitioned into r sets V 1, ..., V r so that the maximum degree of the graph induced by V i is at most d i for each i ∈ { 1, ..., r } . For a given pair ( g, d 1 ), the question of determining the minimum d 2 = d 2 ( g, d 1 ) such that planar graphs with girth at least g are ( d 1, d 2 ) ‐colorable has attracted much interest. The finiteness of d 2 ( g, d 1 ) was known for all cases except when ( g, d 1 ) = ( 5, 1 ) . Montassier and Ochem explicitly asked if d 2 (5, 1) is finite. We answer this question in the affirmative with d 2 ( 5, 1 ) ≤ 10 ; namely, we prove that all planar graphs with girth at least five are (1, 10)‐colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a K = K ( γ ) where graphs with girth at least five that are embeddable on S are (1, K )‐colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least five are (0, k )‐colorable.