论文标题
集团色数的紧密界限
Tight Bounds on the Clique Chromatic Number
论文作者
论文摘要
图形的集团色素数是为其顶点着色所需的最小颜色数量，因此，没有包含在内的最大集合，这不是孤立的顶点是单色的。我们表明，每个最大程度$δ$的图都有clique色度$ o \ left（\fracδ{\ log〜δ} \ right）$。我们获得的推论是，每个$ n $ vertex图都有clique chalomatic number $ o \ left（\ sqrt {\ frac {n} {\ log〜n}}} \ right）$。这两个结果都很紧。
The clique chromatic number of a graph is the minimum number of colours needed to colour its vertices so that no inclusion-wise maximal clique which is not an isolated vertex is monochromatic. We show that every graph of maximum degree $Δ$ has clique chromatic number $O\left(\fracΔ{\log~Δ}\right)$. We obtain as a corollary that every $n$-vertex graph has clique chromatic number $O\left(\sqrt{\frac{n}{\log ~n}}\right)$. Both these results are tight.
