(1, k)‐Coloring of Graphs with Girth at Least Five on a Surface |
| |
| Authors: | Hojin Choi Ilkyoo Choi Jisu Jeong Geewon Suh |
| |
| Institution: | 1. DEPARTMENT OF MATHEMATICAL SCIENCES, KAIST, DAEJEON, REPUBLIC OF KOREA;2. DEPARTMENT OF MATHEMATICAL SCIENCES, KAIST, DAEJEON, REPUBLIC OF KOREAContract grant sponsor: National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP);3. contract grant number: NRF‐2015R1C1A1A02036398;4. contract grant number: GS501100003725 NRF‐2015R1C1A1A02036398. |
| |
| Abstract: | A graph is  ‐colorable if its vertex set can be partitioned into r sets  so that the maximum degree of the graph induced by  is at most  for each  . For a given pair  , the question of determining the minimum  such that planar graphs with girth at least g are  ‐colorable has attracted much interest. The finiteness of  was known for all cases except when  . Montassier and Ochem explicitly asked if d2(5, 1) is finite. We answer this question in the affirmative with  ; 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  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. |
| |
| Keywords: | improper coloring discharging graphs on surfaces |
|
|
‐colorable if its vertex set can be partitioned into r sets 
so that the maximum degree of the graph induced by 
is at most 
for each 
. For a given pair 
, the question of determining the minimum 
such that planar graphs with girth at least g are 
‐colorable has attracted much interest. The finiteness of 
was known for all cases except when 
. Montassier and Ochem explicitly asked if d2(5, 1) is finite. We answer this question in the affirmative with 
; 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 
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.