Optimal chromatic bound for ($P_2\cup P_4$, HVN)-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909911059791872 |
|---|---|
| author | Chen, Lizhong Wang, Hongyang |
| author_facet | Chen, Lizhong Wang, Hongyang |
| contents | The HVN is a graph formed by removing two edges incident to the same vertex from the complete graph $K_5$. In this paper, we prove that every ($P_2\cup P_4$, HVN)-free graph $G$ satisfies $χ(G)\leq\lceil\frac{4}{3}ω(G)\rceil$ when $ω(G)\ge4$, where $χ(G)$ and $ω(G)$ denote the chromatic number and clique number of $G$, respectively. Furthermore, this bound is optimal for every $ω(G)\ge4$. Constructions demonstrating the optimality of the bound are provided. Our work unifies several previously known results on $χ$-binding functions for several graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14507 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal chromatic bound for ($P_2\cup P_4$, HVN)-free graphs Chen, Lizhong Wang, Hongyang Combinatorics 05C15, 05C17, 05C69, 05C75 The HVN is a graph formed by removing two edges incident to the same vertex from the complete graph $K_5$. In this paper, we prove that every ($P_2\cup P_4$, HVN)-free graph $G$ satisfies $χ(G)\leq\lceil\frac{4}{3}ω(G)\rceil$ when $ω(G)\ge4$, where $χ(G)$ and $ω(G)$ denote the chromatic number and clique number of $G$, respectively. Furthermore, this bound is optimal for every $ω(G)\ge4$. Constructions demonstrating the optimality of the bound are provided. Our work unifies several previously known results on $χ$-binding functions for several graph classes. |
| title | Optimal chromatic bound for ($P_2\cup P_4$, HVN)-free graphs |
| topic | Combinatorics 05C15, 05C17, 05C69, 05C75 |
| url | https://arxiv.org/abs/2511.14507 |