The chromatic number of heptagraphs

A hole is an induced cycle of length at least 4. A graph is called a pentagraph if it has no cycles of length 3 or 4 and has no holes of odd length at least 7, and is called a heptagraph if it has no cycles of length less than 7 and has no holes of odd length at least 9. Let \(\l\ge 2\) be an intege...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-06
Main Authors: Wu, Di, Xu, Baogang, Xu, Yian
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A hole is an induced cycle of length at least 4. A graph is called a pentagraph if it has no cycles of length 3 or 4 and has no holes of odd length at least 7, and is called a heptagraph if it has no cycles of length less than 7 and has no holes of odd length at least 9. Let \(\l\ge 2\) be an integer. The current authors proved that a graph is 4- colorable if it has no cycles of length less than \(2\l+1\) and has no holes of odd length at least \(2\l+3\). Confirming a conjecture of Plummer and Zha, Chudnovsky and Seymour proved that every pentagraph is 3-colorable. Following their idea, we show that every heptagraph is 3-colorable.
ISSN:2331-8422