Abstract
We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle C5 and no induced 6-vertex path P6.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 262-285 |
| Number of pages | 24 |
| Journal | Journal of Graph Theory |
| Volume | 84 |
| Issue number | 3 |
| DOIs | |
| State | Published - Mar 1 2017 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Keywords
- algorithm
- coloring
- induced subgraphs
- path
Fingerprint Dive into the research topics of '4-Coloring P6-Free Graphs with No Induced 5-Cycles'. Together they form a unique fingerprint.
Cite this
Chudnovsky, M., Maceli, P., Stacho, J., & Zhong, M. (2017). 4-Coloring P6-Free Graphs with No Induced 5-Cycles. Journal of Graph Theory, 84(3), 262-285. https://doi.org/10.1002/jgt.22025