Counterexample to Babai's lonely colour conjecture
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910637716668416 |
|---|---|
| author | Davies, James Hatzel, Meike Yepremyan, Liana |
| author_facet | Davies, James Hatzel, Meike Yepremyan, Liana |
| contents | Motivated by colouring minimal Cayley graphs, in 1978, Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by constructing graphs of arbitrarily large girth and chromatic number that have a proper edge-colouring in which each cycle contains no colour exactly once. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05199 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Counterexample to Babai's lonely colour conjecture Davies, James Hatzel, Meike Yepremyan, Liana Combinatorics Discrete Mathematics Group Theory 05C15, 05E16, 05C65, 05C25 Motivated by colouring minimal Cayley graphs, in 1978, Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by constructing graphs of arbitrarily large girth and chromatic number that have a proper edge-colouring in which each cycle contains no colour exactly once. |
| title | Counterexample to Babai's lonely colour conjecture |
| topic | Combinatorics Discrete Mathematics Group Theory 05C15, 05E16, 05C65, 05C25 |
| url | https://arxiv.org/abs/2410.05199 |