wovepaper — the arXiv observatory

papers

Publications (7)

math.CO2015

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…

cs.DM2015

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…

cs.DM2014

4-coloring $P_{6}$ -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 $C_{5}$ and no induced 6-vertex path $P_{6}$ .

math.CO2020

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 $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 c…

math.CO2013

Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the $H_{6}$ -conjecture

Maria Chudnovsky, Peter Maceli

Let $G$ 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 $G$ …

math.CO2015

Graphs with no induced five-vertex path or antipath

Maria Chudnovsky, Louis Esperet, Laetitia Lemoine +3

We prove that a graph $G$ contains no induced $5$ -vertex path and no induced complement of a $5$ -vertex path if and only if $G$ is obtained from $5$ -cycles and split graphs by repe…

math.CO2014

Three-coloring graphs with no induced seven-vertex path I : the triangle-free case