컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0538 |
|---|---|
| 분류(Section) | Invited Talk |
| 분과(Session) | Combinatorics / Graph Theory / Cryptography / Coding Theory (SS-05) |
| 영문제목 (Title(Eng.)) |
Counterexamples to the list square coloring conjecture |
| 저자(Author(s)) |
Seog-Jin Kim1 Konkuk University1 |
| 초록본문(Abstract) | The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. Let $\chi(H)$ and $\chi_l(H)$ be the chromatic number and the list chromatic number of $H$, respectively. A graph $H$ is called {\em chromatic-choosable} if $\chi_l (H) = \chi(H)$. It is an interesting problem to find graphs that are chromatic-choosable. Kostochka and Woodall (1997) conjectured that $\chi_l(G^2) = \chi(G^2)$ 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 $\chi_l(G^2) - \chi(G^2)$ can be arbitrary large. This is joint work with Boram Park. |
| 분류기호 (MSC number(s)) |
05C15 |
| 키워드(Keyword(s)) | list coloring, square of graph, chromatic-choosable |
| 강연 형태 (Language of Session (Talk)) |
English |