17 citations · 58 across the 10 of their papers we have counts for
11 papers
3-Coloring -Free Graphs With Only One Prescribed Induced Odd Cycle Length
Yidong Zhou, Mingxian Zhong, Shenwei Huang
A graph is -free if it contains no induced subgraph isomorphic to a -vertex path. A graph is not bipartite if and only if it contains an induced subgraph isomorphic to a $k…
List-three-coloring -free graphs with no induced 1-subdivision of
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
Let and be positive integers. We use to denote the path with vertices and to denote the complete bipartite graph with parts of size and respecti…
Complexity of -coloring in hereditary classes of graphs
Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski +2
For a graph , a graph is \emph{-free} if it does not contain an induced subgraph isomorphic to . For two graphs and , an \emph{-coloring} of is a mapping…
List-three-coloring graphs with no induced
Maria Chudnovsky, Shenwei Huang, Sophie Spirkl +1
For an integer , the graph has components, one of which is a path on vertices, and each of the others is a path on vertices. In this paper we provide a…
Obstructions for three-coloring and list three-coloring -free graphs
Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt +1
A graph is -free if it has no induced subgraph isomorphic to . We characterize all graphs for which there are only finitely many minimal non-three-colorable -free grap…
Approximately coloring graphs without long induced paths
Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl +2
It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on vertices, for fixed . We…
Obstructions for three-coloring graphs without induced paths on six vertices
Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt +1
We prove that there are 24 4-critical -free graphs, and give the complete list. We remark that, if is connected and not a subgraph of , there are infinitely many 4-cr…
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…
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 .