The connection between the chromatic numbers of a hypergraph and its $1$-intersection graph
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_ | 1866914837863333888 |
|---|---|
| author | Blázsik, Zoltán L. Lemons, Nathan W. |
| author_facet | Blázsik, Zoltán L. Lemons, Nathan W. |
| contents | A well known problem from an excellent book of Lovász states that any hypergraph with the property that no pair of hyperedges intersect in exactly one vertex can be properly 2-colored. Motivated by this as well as recent works of Keszegh and of Gyárfás et al we study the $1$-intersection graph of a hypergraph. The $1$-intersection graph encodes those pairs of hyperedges in a hypergraph that intersect in exactly one vertex. We prove for $k\in\{2,4\}$ that all hypergraphs whose $1$-intersection graph is $k$-partite can be properly $k$-colored. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_12118 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The connection between the chromatic numbers of a hypergraph and its $1$-intersection graph Blázsik, Zoltán L. Lemons, Nathan W. Combinatorics 05C15 A well known problem from an excellent book of Lovász states that any hypergraph with the property that no pair of hyperedges intersect in exactly one vertex can be properly 2-colored. Motivated by this as well as recent works of Keszegh and of Gyárfás et al we study the $1$-intersection graph of a hypergraph. The $1$-intersection graph encodes those pairs of hyperedges in a hypergraph that intersect in exactly one vertex. We prove for $k\in\{2,4\}$ that all hypergraphs whose $1$-intersection graph is $k$-partite can be properly $k$-colored. |
| title | The connection between the chromatic numbers of a hypergraph and its $1$-intersection graph |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2406.12118 |