Back to Search
Start Over
FOUR-COLORING \bfitP \bfsix -FREE GRAPHS. I. EXTENDING AN EXCELLENT PRECOLORING.
- Source :
-
SIAM Journal on Computing . 2024, Vol. 53 Issue 1, p111-145. 35p. - Publication Year :
- 2024
-
Abstract
- This is the first paper in a series whose goal is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial-time algorithm that determines if a special kind of precoloring of a P6-free graph has a precoloring extension, and constructs such an extension if one exists. Combined with the main result of the second paper of the series, this gives a complete solution to the problem. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH connectivity
*POLYNOMIAL time algorithms
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 53
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 176201221
- Full Text :
- https://doi.org/10.1137/18M1234837