The difference between the chromatic and the cochromatic number of a random graph
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917929614835712 |
|---|---|
| author | Heckel, Annika |
| author_facet | Heckel, Annika |
| contents | The cochromatic number $ζ(G)$ of a graph $G$ is the minimum number of colours needed for a vertex colouring where every colour class is either an independent set or a clique. Let $χ(G)$ denote the usual chromatic number. Around 1991 Erdős and Gimbel asked: For the random graph $G \sim G_{n, 1/2}$, does $χ(G)-ζ(G) \rightarrow \infty$ whp? Erdős offered \$100 for a positive and \$1,000 for a negative answer.
We give a positive answer to this question for roughly 95% of all values $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_17614 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The difference between the chromatic and the cochromatic number of a random graph Heckel, Annika Combinatorics 05C15, 05C80 The cochromatic number $ζ(G)$ of a graph $G$ is the minimum number of colours needed for a vertex colouring where every colour class is either an independent set or a clique. Let $χ(G)$ denote the usual chromatic number. Around 1991 Erdős and Gimbel asked: For the random graph $G \sim G_{n, 1/2}$, does $χ(G)-ζ(G) \rightarrow \infty$ whp? Erdős offered \$100 for a positive and \$1,000 for a negative answer. We give a positive answer to this question for roughly 95% of all values $n$. |
| title | The difference between the chromatic and the cochromatic number of a random graph |
| topic | Combinatorics 05C15, 05C80 |
| url | https://arxiv.org/abs/2409.17614 |