Nearly optimal coloring of some C4-free graphs

Abstract

A class $\mathcal{G}$ of graphs is $\chi$-{\em polydet} if $\mathcal{G}$ has a polynomial binding function $f$ and there is a polynomial time algorithm to determine an $f(\omega (G))$-coloring of $G\in \mathcal{G}$. Let $P_t$ and $C_t$ denote a path and a cycle on $t$ vertices, respectively. A {\em bull} consists of a triangle with two disjoint pendant edges, a {\em hammer} is obtained by identifying an end of $P_3$ with a vertex of a triangle, a {\em fork${}^{+}$} is obtained from $K_{1,3}$ by subdividing an edge twice. Let $H$ be a bull or a hammer, and $F$ be a $P_7$ or a fork${}^{+}$. We determine all $(C_3,C_4,F)$-free graphs without clique cutsets and universal cliques, and present a close relation between $(C_4,F,H)$-free graphs and the Petersen graph. As a consequence, we show that the classes of $(C_4,F,H)$-free graphs are $\chi$-polydet with nearly optimal linear binding functions.