Posts Tagged ‘최일규’

Ilkyoo Choi (최일규), Largest 2-regular subgraphs in 3-regular graphs

Wednesday, October 31st, 2018
Largest 2-regular subgraphs in 3-regular graphs
Ilkyoo Choi (최일규)
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.

Ilkyoo Choi (최일규), Improper coloring graphs on surfaces

Monday, March 7th, 2016
Improper coloring graphs on surfaces
Ilkyoo Choi (최일규)
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.

1st Korean Workshop on Graph Theory

Tuesday, July 28th, 2015
1st Korean Workshop on Graph Theory
August 26-28, 2015
KAIST  (E6-1 1501 & 3435)
  • Program Book
  • Currently, we are planning to have talks in KOREAN.
  • Students/postdocs may get the support for the accommodation. (Hotel Interciti)
  • Others may contact us if you wish to book a hotel at a pre-negotiated price. Please see the website.
  • We may or may not have contributed talks. If you want, please contact us.
Location: KAIST
  • Room 1501 of E6-1 (August 26, 27)
  • Room 3435 of E6-1 (August 28)
Invited Speakers:

2014 KAIST CMC Discrete Math Workshop

Sunday, November 23rd, 2014
December 10–12, 2014
자연과학동(E6-1), KAIST

Preregistration in deadline: Dec. 5 (Friday)

Program (Dec.10 Wed-Room 1409)
  • 1:30-2:00 Registration
  • 2:00-2:30 Young Soo Kwon (권영수), Yeungnam University: A variation of list coloring and its properties
  • 2:40-3:10 Mitsugu Hirasaka, Pusan National University: Small topics on association schemes
  • 3:10-3:40 Coffee Break
  • 3:40-4:10 Younjin Kim (김연진),  KAIST: On Extremal Combinatorial Problems of Noga Alon
  • 4:20-4:50 Jang Soo Kim (김장수),  Sungkyunkwan University: A new q-Selberg integral, Schur functions, and Young books
  • 5:00-6:00 Discussion
  • 6:00- Dinner
Program (Dec.11 Thurs-Room 1501 & 3435)
Program (Dec.12 Fri-Room 1501)

Ilkyoo Choi, Choosability of Toroidal Graphs with Forbidden Structures

Saturday, March 15th, 2014
Choosability of Toroidal Graphs with Forbidden Structures
2014/07/07 Monday 4PM-5PM
Room 1409
The choosability \(\chi_\ell(G)\) 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 \(\chi_\ell(G)\leq 7\), and \(\chi_\ell(G)=7\) if and only if G contains \(K_7\). Cai, Wang, and Zhu proved that a toroidal graph G without 7-cycles is 6-choosable, and \(\chi_\ell(G)=6\) if and only if G contains \(K_6\). They also prove that a toroidal graph G without 6-cycles is 5-choosable, and conjecture that \(\chi_\ell(G)=5\) if and only if G contains \(K_5\). We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither \(K_5\) 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 \(K^-_5\) (a \(K_5\) 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.