paper

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

arXiv:2111.10469

Abstract

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

arXiv comment17 pages, 1 figure