17 citations · 56 across the 8 of their papers we have counts for
3 papers · 2 filters
Graphs with no induced five-vertex path or antipath
Maria Chudnovsky, Louis Esperet, Laetitia Lemoine +3
We prove that a graph contains no induced -vertex path and no induced complement of a -vertex path if and only if is obtained from -cycles and split graphs by repe…
Better 3-coloring algorithms: excluding a triangle and a seven vertex path
Flavia Bonomo-Braberman, Maria Chudnovsky, Jan Goedgebeur +4
We present an algorithm to color a graph with no triangle and no induced -vertex path (i.e., a -free graph), where every vertex is assigned a list of possible c…
Three-coloring graphs with no induced seven-vertex path I : the triangle-free case
Maria Chudnovsky, Peter Maceli, Mingxian Zhong
In this paper, we give a polynomial time algorithm which determines if a given triangle-free graph with no induced seven-vertex path is 3-colorable, and gives an explicit coloring…