TimeSpeaker/ Title/ Abstract/ VODLocation
16:30 - 17:30 Improper coloring of planar graphs
Ilkyoo Choi (KASIT),
A graph is $(d_1, \ldots, d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, \ldots, V_r$ where the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $i\in \{1, \ldots r\}$. For improper coloring of planar graphs with two parts, given $g$ and $d_1$, the question of determining the minimum $d_2=d_2(g, d_1)$ such that planar graphs with girth $g$ are $(d_1, d_2)$-colorable has attracted much interest. The finiteness of $d_2(g, d_1)$ is known for all cases except when $(g, d_1)=(5, 1)$. Montassier and Ochem, as well as Rapaud, asked if $d_2(5, 1)$ is finite. We answer this question in the affirmative with $d_2(5, 1)\leq 10$; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$-colorable. Moreover, we prove that for any Euler genus $\gamma$, there exists a $K=K(\gamma)$ where graphs with girth $5$ that are embeddable on a surface of Euler genus $\gamma$ are $(1, K)$-colorable. This is joint work with H. Choi, J. Jeong, and G. Suh.
CAMP seminar room