KAIST Discrete Math Seminar

For a graph G, let f₂(G) denote the largest number of vertices in a 2-regular subgraph of G. We determine the minimum of f₂(G) over 3-regular n-vertex simple graphs G.
To do this, we prove that every 3-regular multigraph with exactly c cut-edges has a 2-regular subgraph that omits at most max{0,⎣(c-1)/2⎦} vertices.
More generally, every n-vertex multigraph with maximum degree 3 and m edges has a 2-regular subgraph that omits at most max{0, ⎣(3n-2m+c-1)/2⎦} vertices.
These bounds are sharp; we describe the extremal multigraphs.
This is joint work with Ringi Kim, Alexandr V. Kostochka, Boram Park, and Douglas B. West.

A graph is (d₁, …, d_r)-colorable if its vertex set can be partitioned into r sets V₁, …, 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₁, …, d_r, determining if a (sparse) graph is (d₁, …, 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₁ and d₂, there exists a planar graph that is not (d₁, d₂)-colorable.
Therefore, it is natural to study the question for planar graphs with girth conditions.
Namely, given g and d₁, determine the minimum d₂=d₂(g, d₁) such that planar graphs with girth g are (d₁, d₂)-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₁, …, 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₁, …, 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₁(γ))-colorable and (2, 2, K₂(γ))-colorable, where K₁(γ) and K₂(γ) 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.

The choosability of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that , and if and only if G contains . Cai, Wang, and Zhu proved that a toroidal graph G without 7-cycles is 6-choosable, and if and only if G contains . They also prove that a toroidal graph G without 6-cycles is 5-choosable, and conjecture that if and only if G contains . We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither (a missing one edge) nor 6-cycles are 4-choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4-choosable.