3 results
A NOTE ON
$\chi $-BINDING FUNCTIONS AND LINEAR FORESTS
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society , First View
- Published online by Cambridge University Press:
- 27 September 2024, pp. 1-7
-
- Article
-
- You have access
- HTML
- Export citation
-
Let G and H be two vertex disjoint graphs. The join
$G+H$ is the graph with 
$V(G+H)=V(G)+V(H)$ and 
$E(G+H)=E(G)\cup E(H)\cup \{xy\;|\; x\in V(G), y\in V(H)\}$. A (finite) linear forest is a graph consisting of (finite) vertex disjoint paths. We prove that for any finite linear forest F and any nonnull graph H, if 
$\{F, H\}$-free graphs have a 
$\chi $-binding function 
$f(\omega )$, then 
$\{F, K_n+H\}$-free graphs have a 
$\chi $-binding function 
$kf(\omega )$ for some constant k.
THE CHROMATIC NUMBER OF
$\boldsymbol {(P_6,C_4,\mbox {diamond})}$-FREE GRAPHS
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society / Volume 108 / Issue 1 / August 2023
- Published online by Cambridge University Press:
- 03 October 2022, pp. 1-10
- Print publication:
- August 2023
-
- Article
- Export citation
-
The diamond is the complete graph on four vertices minus one edge;
$P_n$ and 
$C_n$ denote the path and cycle on n vertices, respectively. We prove that the chromatic number of a 
$(P_6,C_4,\mbox {diamond})$-free graph G is no larger than the maximum of 3 and the clique number of G.
1 - Clique-width for hereditary graph classes
-
-
- Book:
- Surveys in Combinatorics 2019
- Published online:
- 17 June 2019
- Print publication:
- 27 June 2019, pp 1-56
-
- Chapter
-
- You have access
- Export citation
