17 citations · 56 across the 8 of their papers we have counts for
6 papers · 1 filter
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…
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…
Excluding four-edge paths and their complements
Maria Chudnovsky, Peter Maceli, Irena Penev
We prove that a graph G contains no induced four-edge path and no induced complement of a four-edge path if and only if G is obtained from five-cycles and split graphs by repeatedl…
Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the -conjecture
Maria Chudnovsky, Peter Maceli
Let be the class of all graphs with no induced four-edge path or four-edge antipath. Hayward and Nastos \cite{MS} conjectured that every prime graph in …