Chromatic number and regular subgraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912056794415104 |
|---|---|
| author | Janzer, Barnabás Steiner, Raphael Sudakov, Benny |
| author_facet | Janzer, Barnabás Steiner, Raphael Sudakov, Benny |
| contents | In 1992, Erdős and Hajnal posed the following natural problem: Does there exist, for every $r\in \mathbb{N}$, an integer $F(r)$ such that every graph with chromatic number at least $F(r)$ contains $r$ edge-disjoint cycles on the same vertex set? We solve this problem in a strong form, by showing that there exist $n$-vertex graphs with fractional chromatic number $Ω\left(\frac{\log \log n}{\log \log \log n}\right)$ that do not even contain a $4$-regular subgraph. This implies that no such number $F(r)$ exists for $r\ge 2$. We show that assuming a conjecture of Harris, the bound on the fractional chromatic number in our result cannot be improved. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02437 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Chromatic number and regular subgraphs Janzer, Barnabás Steiner, Raphael Sudakov, Benny Combinatorics 05C15, 05C70, 05C80 In 1992, Erdős and Hajnal posed the following natural problem: Does there exist, for every $r\in \mathbb{N}$, an integer $F(r)$ such that every graph with chromatic number at least $F(r)$ contains $r$ edge-disjoint cycles on the same vertex set? We solve this problem in a strong form, by showing that there exist $n$-vertex graphs with fractional chromatic number $Ω\left(\frac{\log \log n}{\log \log \log n}\right)$ that do not even contain a $4$-regular subgraph. This implies that no such number $F(r)$ exists for $r\ge 2$. We show that assuming a conjecture of Harris, the bound on the fractional chromatic number in our result cannot be improved. |
| title | Chromatic number and regular subgraphs |
| topic | Combinatorics 05C15, 05C70, 05C80 |
| url | https://arxiv.org/abs/2410.02437 |