Largest 2-regular subgraphs in 3-regular graphs
Ilkyoo Choi (최일규)
Department of Mathematics, Hankuk University of Foreign Studies, Yongin-si
Department of Mathematics, Hankuk University of Foreign Studies, Yongin-si
2018/11/26 Mon 5PM-6PM (Bldg. E6-1, Room 1401)
For a graph G, let f2(G) denote the largest number of vertices in a 2-regular subgraph of G. We determine the minimum of f2(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.
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.
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 
(a