On the 3‐Colorability of Triangle‐Free and Fork‐Free Graphs
Abstract
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.
Fields of Study & Subjects
Graph Labeling and Dimension Problems
Advanced Graph Theory Research
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Journal of Graph Theory
- Publication date
- 30 July 2026
- Language
- EN