Families of Linearly $\chi$-bounded Graphs without Chair or its Induced Sub-graphs

Abstract

A hereditary class H of graphs is $\chi$-bounded if there is a $\chi$-binding function f such that for every $G$ in $H$, $\chi (G)$ less than or equal to $f(\omega (G))$. Here we prove that if a graph $G$ is free of 1. {Chair; P${}_4$+K${}_1$} or 2. {Chair; HVN}, then $\chi (G)$ is linearly bounded by maximum clique size of G. We further prove that if $G$ is free of 3. {P${}_4$+K${}_1$; P${}_3$ $\cup$ K${}_1$} or 4. {P4+K1; K${}_2$ $\cup$ 2K${}_1$} or 5. {HVN; P${}_3$ $\cup$ K${}_1$} or 6. {HVN; K${}_2$ $\cup$ 2K${}_1$} or 7. {K${}_{5-e}$; P${}_3$ $\cup$ K${}_1$} or 8. {K${}_{5-e}$; K${}_2$ $\cup$ 2K${}_1$}, then there is a tight linear $\chi$-bound for $G$.

16 pages