Posts Tagged ‘최일규’

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)
http://home.kias.re.kr/MKG/h/KWGT2015/
  • 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.
  • PLEASE REGISTER UNTIL AUGUST 16.
Location: KAIST
  • Room 1501 of E6-1 (August 26, 27)
  • Room 3435 of E6-1 (August 28)
Invited Speakers:
Organizers:

2014 KAIST CMC Discrete Math Workshop

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

Preregistration in kcw2014.eventbrite.com 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.

Ilkyoo Choi (최일규), The list version of the Borodin-Kostochka Conjecture for graphs with large maximum degree

Thursday, November 29th, 2012
The list version of the Borodin-Kostochka Conjecture for graphs with large maximum degree
Ilkyoo Choi (최일규)
Department of Mathematics, University of Illinois at Urbana-Champaign, IL, USA
2012/12/27 Thu 4PM-5PM
Brooks’ Theorem states that for a graph G with maximum degree Δ(G) at least 3, the chromatic number is at most Δ(G) when the clique number is at most Δ(G). Vizing proved that the list chromatic number is also at most Δ(G) under the same conditions. Borodin and Kostochka conjectured that a graph G with maximum degree at least 9 must be (Δ(G)-1)-colorable when the clique number is at most Δ(G)-1; this was proven for graphs with maximum degree at least 1014 by Reed. We prove an analogous result for the list chromatic number; namely, we prove that a graph G with Δ(G)≥ 1020 is (Δ(G)-1)-choosable when the clique number is at most Δ(G)-1. This is joint work with H. A. Kierstead, L. Rabern, and B. Reed.