Tight Bounds on the Clique Chromatic Number
| Autor: | Piotr Micek, Gwenaël Joret, Michiel Smid, Bruce Reed |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Mathematics::Combinatorics Discrete Mathematics (cs.DM) Applied Mathematics Géométrie Clique (graph theory) Theoretical Computer Science Vertex (geometry) Combinatorics Computational Theory and Mathematics Computer Science::Discrete Mathematics Informatique mathématique FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Graph (abstract data type) Combinatorics (math.CO) Geometry and Topology Chromatic scale Computer Science - Discrete Mathematics Mathematics |
| Zdroj: | The electronic journal of combinatorics, 28 (3 |
| ISSN: | 1077-8926 |
| Popis: | 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 (∆ log ∆ (√ n-vertex graph has clique chromatic number On). We obtain as a corollary that every). Both these results are tight. SCOPUS: ar.j info:eu-repo/semantics/published |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|