FOUR-COLORING P6-FREE GRAPHS. II. FINDING AN EXCELLENT PRECOLORING

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

Abstract

This is the second paper in a series of two. The goal of the series 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 starts with a 4-precoloring of a graph with no induced six-vertex path and outputs a polynomial-sized collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem.

Original languageEnglish (US)
Pages (from-to)146-187
Number of pages42
JournalSIAM Journal on Computing
Volume53
Issue number1
DOIs
StatePublished - 2024

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Keywords

  • algorithm
  • coloring
  • induced subgraph
  • path

Fingerprint

Dive into the research topics of 'FOUR-COLORING P6-FREE GRAPHS. II. FINDING AN EXCELLENT PRECOLORING'. Together they form a unique fingerprint.

Cite this