论文标题
朝着加莱的猜想的紧密界限
Tight bounds towards a conjecture of Gallai
论文作者
论文摘要
我们证明，对于$ n> k \ geq 3 $，如果$ g $是带有色度$ k $的$ n $ vertex图，但其适当的子图的任何适当的子图具有较小的色度，则$ g $最多包含$ n-k+3 $ copies size $ k-k-1 $。这回答了雅培和周的一个问题，并在加莱的猜想上提供了紧密的束缚。
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.
