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

### Abstract

We present an algorithm to color a graph G with no triangle and no induced 7-vertex path (i.e., a {P-7, C-3}-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(vertical bar V (G)vertical bar(5)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)), and if G is bipartite, it improves to O(vertical bar V (G)vertical bar(2)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)). Moreover, we prove that there are finitely many minimal obstructions to list 3-coloring {P-t, C-3}-free graphs if and only if t = 7. This implies the existence of a polynomial time certifying algorithm for list 3-coloring in {P-7, C-3}-free graphs. We furthermore determine other cases of t, l, and k such that the family of minimal obstructions to list k-coloring in {P-t, C-l}-free graphs is finite. (C) 2020 Elsevier B.V. All rights reserved.

### Más información

Título según WOS: | Better 3-coloring algorithms: Excluding a triangle and a seven vertex path |

Título de la Revista: | THEORETICAL COMPUTER SCIENCE |

Volumen: | 850 |

Editorial: | Elsevier |

Fecha de publicación: | 2021 |

Página de inicio: | 98 |

Página final: | 115 |

DOI: |
10.1016/j.tcs.2020.10.032 |

Notas: | ISI |