|
2025-10-14 / 16:30 ~ 17:30
|
| IBS-KAIST 세미나 - 이산수학: An improved lower bound on the number of edges in list critical graphs via DP coloring |

|
|
by Ilkyoo Choi(Department of Mathematics, Hankuk University of Fo)
|
A graph $G$ is (list, DP) $k$-critical if the (list, DP) chromatic number is $k$ but for every proper subgraph $G’$ of $G$, the (list, DP) chromatic number of $G’$ is less than $k$. For $k\geq 4$, we show a bound on the minimum number of edges in a DP $k$-critical graph, and our bound is the first bound that is asymptotically better than the corresponding bound for proper $k$-critical graphs by Gallai from 1963. Our result also improves the best bound on the list chromatic number. This is joint work with Bradshaw, Kostochka, and Xu.
|
|
|