기초과학연구원 이산수학그룹
On August 30, 2022, Jun Gao (高峻) from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar about the tight upper bound on the number of (k-1)-cliques in a k-critical graph, solving the conjecture of Abbott and Zhou in 1992. The title of his talk was “Number of (k-1)-cliques in k-critical graph“.
We prove that for $n>k\geq 3$, if $G$ is an $n$-vertex graph with chromatic number $k$ but any its proper subgraph has smaller chromatic number, then $G$ contains at most $n-k+3$ copies of cliques of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai.
This is joint work with Jie Ma.
The IBS Discrete Mathematics Group welcomes Dr. Jun Gao (高峻), a new (and second) research fellow at the IBS Extremal Combinatorics and Probability Group from August 1, 2022. He received his Ph.D. from the University of Science and Technology of China (USTC) under the supervision of Prof. Jie Ma.