On the 3-colorability of triangle-free and fork-free graphs

Abstract

A graph $G$ is said to satisfy the Vizing bound if $\chi (G)\le \omega (G)+1$, where $\chi (G)$ and $\omega (G)$ denote the chromatic number and clique number of $G$, respectively. It was conjectured by Randerath in 1998 that if $G$ is a triangle-free and fork-free graph, where the fork (also known as trident) is obtained from $K_{1,4}$ by subdividing two edges, then $G$ satisfies the Vizing bound. In this paper, we confirm this conjecture.

17 pages, 1 figure