Improper coloring graphs on surfaces

Ilkyoo Choi (최일규)

Department of Mathematical Sciences, KAIST

Department of Mathematical Sciences, KAIST

2016/3/9 Wed 4PM-5PM

A graph is (d

Given r and d

For example, the Four Color Theorem states that all planar graphs are 4-colorable, and therefore (0, 0, 0, 0)-colorable.

The question is also well studied for partitioning planar graphs into three parts.

For two parts, it is known that for given d

Therefore, it is natural to study the question for planar graphs with girth conditions.

Namely, given g and d

Given integers k, γ, g we completely characterize the smallest k-tuple (d

All of our results are tight, up to a constant multiplicative factor for the degrees d

In particular, we show that a graph embeddable on a surface of Euler genus γ is (0, 0, 0, K

_{1}, …, d_{r})-colorable if its vertex set can be partitioned into r sets V_{1}, …, V_{r}where the maximum degree of the graph induced by V_{i}is at most d_{i}for each i in {1, …, r}.Given r and d

_{1}, …, d_{r}, determining if a (sparse) graph is (d_{1}, …, d_{r})-colorable has attracted much interest.For example, the Four Color Theorem states that all planar graphs are 4-colorable, and therefore (0, 0, 0, 0)-colorable.

The question is also well studied for partitioning planar graphs into three parts.

For two parts, it is known that for given d

_{1}and d_{2}, there exists a planar graph that is not (d_{1}, d_{2})-colorable.Therefore, it is natural to study the question for planar graphs with girth conditions.

Namely, given g and d

_{1}, determine the minimum d_{2}=d_{2}(g, d_{1}) such that planar graphs with girth g are (d_{1}, d_{2})-colorable. We continue the study and ask the same question for graphs that are embeddable on a fixed surface.Given integers k, γ, g we completely characterize the smallest k-tuple (d

_{1}, …, d_{k}) in lexicographical order such that each graph of girth at least g that is embeddable on a surface of Euler genus γ is (d_{1}, …, d_{k})-colorable.All of our results are tight, up to a constant multiplicative factor for the degrees d

_{i}depending on g.In particular, we show that a graph embeddable on a surface of Euler genus γ is (0, 0, 0, K

_{1}(γ))-colorable and (2, 2, K_{2}(γ))-colorable, where K_{1}(γ) and K_{2}(γ) are linear functions in γ.This talk is based on results and discussions with H. Choi, F. Dross, L. Esperet, J. Jeong, M. Montassier, P. Ochem, A. Raspaud, and G. Suh.