Name
Abstract | ||
|---|---|---|
In this paper, we give a polynomial time algorithm which determines if a given graph containing a triangle and no induced seven-vertex path is 3-colorable, and gives an explicit coloring if one exists. In previous work, we gave a polynomial time algorithm for three-coloring triangle-free graphs with no induced seven-vertex path. Combined, our work shows that three-coloring a graph with no induced seven-vertex path can be done in polynomial time. |
Year | Venue | Field |
|---|---|---|
2015 | CoRR | Discrete mathematics,Combinatorics,Indifference graph,Induced path,Chordal graph,Cograph,Pathwidth,1-planar graph,Longest path problem,Mathematics,Graph coloring |
DocType | Volume | Citations |
Journal | abs/1503.03573 | 1 |
PageRank | References | Authors |
0.37 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 15 | 4.18 |
| Peter Maceli | 2 | 13 | 4.47 |
| Mingxian Zhong | 3 | 4 | 1.48 |