Some Cases of the Erdős-Lovász Tihany Conjecture for Claw-free Graphs
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_ | 1866914857749577728 |
|---|---|
| author | Longbrake, Sean Tariq, Juvaria |
| author_facet | Longbrake, Sean Tariq, Juvaria |
| contents | The Erdős-Lovász Tihany Conjecture states that any $G$ with chromatic number $χ(G) = s + t - 1 > ω(G)$, with $s,t \geq 2$ can be split into two vertex-disjoint subgraphs of chromatic number $s, t$ respectively. We prove this conjecture for pairs $(s, t)$ if $t \leq s + 2$, whenever $G$ has a $K_s$, and for pairs $(s, t)$ if $t \leq 4 s - 3$, whenever $G$ contains a $K_s$ and is claw-free. We also prove the Erdős Lovász Tihany Conjecture for the pair $(3, 10)$ for claw-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15164 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Some Cases of the Erdős-Lovász Tihany Conjecture for Claw-free Graphs Longbrake, Sean Tariq, Juvaria Combinatorics 05C15 The Erdős-Lovász Tihany Conjecture states that any $G$ with chromatic number $χ(G) = s + t - 1 > ω(G)$, with $s,t \geq 2$ can be split into two vertex-disjoint subgraphs of chromatic number $s, t$ respectively. We prove this conjecture for pairs $(s, t)$ if $t \leq s + 2$, whenever $G$ has a $K_s$, and for pairs $(s, t)$ if $t \leq 4 s - 3$, whenever $G$ contains a $K_s$ and is claw-free. We also prove the Erdős Lovász Tihany Conjecture for the pair $(3, 10)$ for claw-free graphs. |
| title | Some Cases of the Erdős-Lovász Tihany Conjecture for Claw-free Graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2406.15164 |