Back to Search Start Over

Coloring [formula omitted]-free graphs with [formula omitted] colors.

Authors :
Chen, Rong
Lan, Kaiyang
Zhou, Yidong
Source :
Discrete Applied Mathematics. Jan2024, Vol. 342, p12-18. 7p.
Publication Year :
2024

Abstract

A house is the graph that consists of an induced 4-vertex cycle and a single vertex with precisely two adjacent neighbors on the cycle. The Borodin–Kostochka Conjecture states that for each graph G with Δ (G) ≥ 9 , we have χ (G) ≤ max { Δ (G) − 1 , ω (G) }. We show that this conjecture holds for { P 2 ∪ P 3 , house } -free graphs. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
0166218X
Volume :
342
Database :
Academic Search Index
Journal :
Discrete Applied Mathematics
Publication Type :
Academic Journal
Accession number :
173860019
Full Text :
https://doi.org/10.1016/j.dam.2023.09.003