Skip to main content

4-coloring $P_6$-free graphs with no induced 5-cycles

Author(s): Chudnovsky, Maria; Maceli, Peter; Stacho, Juraj; Zhong, Mingxian

To refer to this page use:
Abstract: We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle $C_5$ and no induced 6-vertex path $P_6$.
Publication Date: Mar-2017
Electronic Publication Date: 12-Feb-2016
Citation: Chudnovsky, Maria, Maceli, Peter, Stacho, Juraj, Zhong, Mingxian. (4-coloring $P_6$-free graphs with no induced 5-cycles
DOI: 10.1002/jgt.22025
Pages: 262-285
Type of Material: Journal Article
Journal/Proceeding Title: Journal of Graph Theory
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.