The perfect divisibility and chromatic number of some odd hole-free graphs
Discrete Applied Mathematics · 2026-07 · 387 · 124-128
DOI: 10.1016/j.dam.2026.03.008 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2026-07. Verfasst von Weihua He und 3 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Gefördert von: National Key Research and Development Program of China, Ministry of Science and Technology of the People's Republic of China.
Abstract (Originalsprache)
A hole is an induced cycle of length at least 4, and an odd hole is a hole of odd length. It is NP-hard to color the vertices of an odd hole-free graph. A graph $G$ is perfectly divisible if every induced subgraph $H$ of $G$ with at least one edge admits a partition of $V(H)$ into sets $A$ and $B$ such that $H[A]$ is perfect and $\omega(H[B])
Förderung
- National Key Research and Development Program of China
- Ministry of Science and Technology of the People's Republic of China
Zitieren
APA
He, W., Shi, Y., Wu, R., & Yao, Z. (2026). The perfect divisibility and chromatic number of some odd hole-free graphs. Discrete Applied Mathematics, 387, 124-128. https://doi.org/10.1016/j.dam.2026.03.008
Vancouver
He W, Shi Y, Wu R, Yao Z. The perfect divisibility and chromatic number of some odd hole-free graphs. Discrete Applied Mathematics. 2026;387:124-128. doi:10.1016/j.dam.2026.03.008
BibTeX
@article{He2026,
author = {He, Weihua and Shi, Yueping and Wu, Rong and Yao, Zheng-an},
title = {The perfect divisibility and chromatic number of some odd hole-free graphs},
journal = {Discrete Applied Mathematics},
year = {2026},
volume = {387},
pages = {124--128},
doi = {10.1016/j.dam.2026.03.008}
}
EUVIMED