## 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(|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 {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,ℓ, and k such that the family of minimal obstructions to list k-coloring in {P_{t},C_{ℓ}}-free graphs is finite.

Original language | English (US) |
---|---|

Pages (from-to) | 98-115 |

Number of pages | 18 |

Journal | Theoretical Computer Science |

Volume | 850 |

DOIs | |

State | Published - Jan 4 2021 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science

## Keywords

- Certifying algorithm
- Forbidden induced subgraphs
- Graph algorithm
- Graph coloring