Odd clique minors and chromatic bounds of {3$K_1$, paraglider}-free graphs

Abstract

A paraglider, house, 4-wheel, is the graph that consists of a cycle $C_4$ plus an additional vertex adjacent to three vertices, two adjacent vertices, all the vertices of the $C_4$, respectively. For a graph $G$, let $\chi (G)$, $\omega (G)$ denote the chromatic number, the clique number of $G$, respectively. Gerards and Seymour from 1995 conjectured that every graph $G$ has an odd $K_{\chi (G)}$ minor. In this paper, based on the description of graph structure, it is shown that every graph $G$ with independence number two satisfies the conjecture if one of the following is true: $\chi (G)\le 2\omega (G)$ when $n$ is even, $\chi (G)\le 9\omega (G)/5$ when $n$ is odd, $G$ is a quasi-line graph, $G$ is $H$-free for some induced subgraph $H$ of paraglider, house or $W_4$. Moreover, we derive an optimal linear $\chi$-binding function for {3$K_1$, paraglider}-free graph $G$ that $\chi (G)\le \max \{\omega (G)+3,2\omega (G)-2\}$, which improves the previous result, $\chi (G)\le 2\omega (G)$, due to Choudum, Karthick and Shalu in 2008.

18 pages, 3 figures