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