Back to Search
Start Over
An optimal chromatic bound for the class of $\{P_3\cup 2K_1,\overline{P_3\cup 2K_1}\}$-free graphs
- Publication Year :
- 2023
-
Abstract
- In 1987, A. Gy\'arf\'as in his paper ``Problems from the world surrounding perfect graphs'' posed the problem of determining the smallest $\chi$-binding function for $\mathcal{G}(F,\overline{F})$, when $\mathcal{G}(F)$ is $\chi$-bounded. So far the problem has been attempted for only forest $F$ with four or five vertices. In this paper, we address the case when $F=P_3\cup 2K_1$ and show that if $G$ is a $\{P_3\cup 2K_1,\overline{P_3\cup 2K_1}\}$-free graph with $\omega(G)\neq 3$, then it admits $\omega(G)+1$ as a $\chi$-binding function. Moreover, we also construct examples to show that this bound is tight for all values of $\omega\neq 3$.
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2311.05231
- Document Type :
- Working Paper