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 (d1, …, dr)-colorable if its vertex set can be partitioned into r sets V1, …, Vr where the maximum degree of the graph induced by Vi is at most di for each i in {1, …, r}.
Given r and d1, …, dr, determining if a (sparse) graph is (d1, …, dr)-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 d1 and d2, there exists a planar graph that is not (d1, d2)-colorable.
Therefore, it is natural to study the question for planar graphs with girth conditions.
Namely, given g and d1, determine the minimum d2=d2(g, d1) such that planar graphs with girth g are (d1, d2)-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 (d1, …, dk) in lexicographical order such that each graph of girth at least g that is embeddable on a surface of Euler genus γ is (d1, …, dk)-colorable.
All of our results are tight, up to a constant multiplicative factor for the degrees di depending on g.
In particular, we show that a graph embeddable on a surface of Euler genus γ is (0, 0, 0, K1(γ))-colorable and (2, 2, K2(γ))-colorable, where K1(γ) and K2(γ) 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.
Given r and d1, …, dr, determining if a (sparse) graph is (d1, …, dr)-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 d1 and d2, there exists a planar graph that is not (d1, d2)-colorable.
Therefore, it is natural to study the question for planar graphs with girth conditions.
Namely, given g and d1, determine the minimum d2=d2(g, d1) such that planar graphs with girth g are (d1, d2)-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 (d1, …, dk) in lexicographical order such that each graph of girth at least g that is embeddable on a surface of Euler genus γ is (d1, …, dk)-colorable.
All of our results are tight, up to a constant multiplicative factor for the degrees di depending on g.
In particular, we show that a graph embeddable on a surface of Euler genus γ is (0, 0, 0, K1(γ))-colorable and (2, 2, K2(γ))-colorable, where K1(γ) and K2(γ) 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.
Tags: 최일규