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