Posts Tagged ‘박보람’

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:

Boram Park (박보람), Counterexamples to the List Square Coloring Conjecture

Wednesday, September 4th, 2013
Counterexamples to the List Square Coloring Conjecture
Boram Park
Optimization and Its Application Research Team
2013/10/16 Wednesday 4PM-5PM
ROOM 1409
The square G2 of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in G2 if the distance between u and v in G is at most 2. Let χ(H) and χl(H) be the chromatic number and the list chromatic number of H, respectively. A graph H is called chromatic-choosable if χl(H) = χ(H). It is an interesting problem to find graphs that are chromatic-choosable. Kostochka and Woodall conjectured that χl(G2) = χ(G2) for every graph G, which is called List Square Coloring Conjecture. In this paper, we give infinitely many counterexamples to the conjecture. Moreover, we show that the value χl(G2) − χ(G2) can be arbitrary large.