TY - JOUR

T1 - Better 3-coloring algorithms

T2 - Excluding a triangle and a seven vertex path

AU - Bonomo-Braberman, Flavia

AU - Chudnovsky, Maria

AU - Goedgebeur, Jan

AU - Maceli, Peter

AU - Schaudt, Oliver

AU - Stein, Maya

AU - Zhong, Mingxian

N1 - Funding Information:
Partially supported by ANPCyT PICT-2015-2218, UBACyT Grants 20020160100095BA and 20020170100495BA (Argentina), and PROGAMA REGIONAL MATHAMSUD MATH190013.Partially supported by NSF grants IIS-1117631, DMS-1001091 and DMS-1265803.Supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO).Supported by FONDECYT Regular Grant 1183080 and by CONICYT + PIA/Apoyo a centros científicos y tecnológicos de excelencia con financiamiento Basal, Código AFB170001, and PROGAMA REGIONAL MATHAMSUD MATH190013.
Publisher Copyright:
© 2020 Elsevier B.V.

PY - 2021/1/4

Y1 - 2021/1/4

N2 - 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.

AB - 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.

KW - Certifying algorithm

KW - Forbidden induced subgraphs

KW - Graph algorithm

KW - Graph coloring

UR - http://www.scopus.com/inward/record.url?scp=85094854389&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85094854389&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2020.10.032

DO - 10.1016/j.tcs.2020.10.032

M3 - Article

AN - SCOPUS:85094854389

SN - 0304-3975

VL - 850

SP - 98

EP - 115

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -