|
|||||
|
|
4‐Coloring P6‐Free Graphs with No Induced 5‐Cycles |
|
| Authors: | Maria Chudnovsky Peter Maceli Juraj Stacho Mingxian Zhong |
| Institution: | 1. DEPARTMENT OF MATHEMATICS, PRINCETON UNIVERSITY, PRINCETON, NJ;2. DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE, WESLEYAN UNIVERSITY, MIDDLETOWN, CT, USA |
| 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 |
| Keywords: | coloring induced subgraphs algorithm path |