DOI: 10.1002/jgt.23094 ISSN: 0364-9024
The chromatic number of heptagraphs
Di Wu, Baogang Xu, Yian Xu- Geometry and Topology
- Discrete Mathematics and Combinatorics
Abstract
A pentagraph is a graph without cycles of length 3 or 4 and without induced cycles of odd length at least 7, and a heptagraph is one without cycles of length less than 7 and without induced cycles of odd length at least 9. Chudnovsky and Seymour proved that every pentagraph is 3‐colorable. In this paper, we show that every heptagraph is 3‐colorable.