## Posts Tagged ‘최일규’

### 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.

### Ilkyoo Choi (최일규), Avoiding Large Squares in Partial Words

Friday, December 2nd, 2011
Avoiding Large Squares in Partial Words
Ilkyoo Choi (최일규)
Department of Mathematics, University of Illinois at Urbana-Champaign, IL, USA
2011/12/22 Thu 4PM-5PM
Given a fixed alphabet, a word of length n is an n-tuple with entries in the alphabet. A hole is a character outside the alphabet that is viewed as representing any letter of the alphabet. A partial word is a string where each character is a hole or belongs to the alphabet. Two partial words having the same length are compatible if they agree at each position where neither has a hole.
A square is a word formed by concatenating two copies of a single word (no holes). A partial word W contains a square S if S is compatible with some (consecutive) subword of W. Let g(h,s) denote the maximum length of a binary partial word with h holes that contains at most s distinct squares. We prove that g(h,s)=∞ when s≥4 and when s=3 with h∈{0,1,2}; otherwise, g(h,s) is finite. Furthermore, we extend our research to cube-free binary partial words.
This is joint work with Dr. Francine Blanchet-Sadri and Robert Mercas.