17 citations · 56 across the 8 of their papers we have counts for
8 papers
Coloring graphs with no induced five-vertex path or gem
M. Chudnovsky, T. Karthick, P. Maceli +1
For a graph , let and respectively denote the chromatic number and clique number of . We give an explicit structural description of (,gem)-free graphs, and…
Three-coloring graphs with no induced seven-vertex path II : using a triangle
Maria Chudnovsky, Peter Maceli, Mingxian Zhong
In this paper, we give a polynomial time algorithm which determines if a given graph containing a triangle and no induced seven-vertex path is 3-colorable, and gives an explicit co…
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…
4-coloring -free graphs with no induced 5-cycles
Maria Chudnovsky, Peter Maceli, Juraj Stacho +1
We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle and no induced 6-vertex path .