| Friday 17 May 2024 | |
| Events for day: Wednesday 08 May 2024 |
| 14:00 - 15:00 Combinatorics and Computing Weekly Seminar The List Square Coloring Conjecture Fails for Bipartite Planar Graphs and their Line Graphs School MATHEMATICS Kostochka and Woodall (2001) conjectured that the square of every graph has the same chromatic number and list chromatic number. In 2015 Kim and Park disproved this conjecture for non-bipartite and bipartite graphs. It was asked by several authors whether this conjecture holds for bipartite graphs with small degrees, claw-free graphs, or line graphs. In this talk, we introduce cubic counterexamples to this conjecture to solve three open problems posed by Kim and Park~(2015), Kim, Kwon, and Park~(2015), and Dai, Wang, Yang, and Yu~(2018). In particular, we disprove a planar version of this conjecture proposed by Havet, Heuvel, McDiarmid, and ... |