Better 3-coloring algorithms: Excluding a triangle and a seven vertex path

Flavia Bonomo-Braberman, Maria Chudnovsky, Jan Goedgebeur, Peter Maceli, Oliver Schaudt, Maya Stein, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

Abstract

We present an algorithm to color a graph G with no triangle and no induced 7-vertex path (i.e., a {P7,C3}-free graph), where every vertex is assigned a list of possible colors which is a subset of {1,2,3}. While this is a special case of the problem solved in Bonomo et al. (2018) [1], that does not require the absence of triangles, the algorithm here is both faster and conceptually simpler. The complexity of the algorithm is O(|V(G)|5(|V(G)|+|E(G)|)), and if G is bipartite, it improves to O(|V(G)|2(|V(G)|+|E(G)|)). Moreover, we prove that there are finitely many minimal obstructions to list 3-coloring {Pt,C3}-free graphs if and only if t≤7. This implies the existence of a polynomial time certifying algorithm for list 3-coloring in {P7,C3}-free graphs. We furthermore determine other cases of t,ℓ, and k such that the family of minimal obstructions to list k-coloring in {Pt,C}-free graphs is finite.

Original languageEnglish (US)
Pages (from-to)98-115
Number of pages18
JournalTheoretical Computer Science
Volume850
DOIs
StatePublished - Jan 4 2021

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Certifying algorithm
  • Forbidden induced subgraphs
  • Graph algorithm
  • Graph coloring

Fingerprint

Dive into the research topics of 'Better 3-coloring algorithms: Excluding a triangle and a seven vertex path'. Together they form a unique fingerprint.

Cite this