Geodesic
Tight bounds on the clique chromatic number
The electronic journal of combinatorics, Tome 28 (2021) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 $\Delta$ has clique chromatic number $O\left(\frac{\Delta}{\log~\Delta}\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.
DOI : 10.37236/9659
Classification : 05C15, 05D40
Mots-clés : clique colouring, perfect graphs 
@article{10_37236_9659,
     author = {Gwena\"el Joret and Piotr Micek and Bruce Reed and Michiel Smid},
     title = {Tight bounds on the clique chromatic number},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {3},
     doi = {10.37236/9659},
     zbl = {1510.05075},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9659/}
}
TY  - JOUR
AU  - Gwenaël Joret
AU  - Piotr Micek
AU  - Bruce Reed
AU  - Michiel Smid
TI  - Tight bounds on the clique chromatic number
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9659/
DO  - 10.37236/9659
ID  - 10_37236_9659
ER  - 
%0 Journal Article
%A Gwenaël Joret
%A Piotr Micek
%A Bruce Reed
%A Michiel Smid
%T Tight bounds on the clique chromatic number
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9659/
%R 10.37236/9659
%F 10_37236_9659
Gwenaël Joret; Piotr Micek; Bruce Reed; Michiel Smid. Tight bounds on the clique chromatic number. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9659

Cité par Sources :