Article ID Journal Published Year Pages File Type
4647791 Discrete Mathematics 2013 6 Pages PDF
Abstract
A graph is 2P3-free if it does not contain two vertex-disjoint paths on three vertices as an induced subgraph. We prove that every triangle-free 2P3-free graph is 4-colorable. This answers an open question posed by Broersma et al.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Triangle-free 2P3-free graphs are 4-colorable
Authors
,