Mingxian Zhong

activity

20142025

most citedThree-coloring graphs with no induced seven-vertex path II : using a triangle

17 citations · 58 across the 10 of their papers we have counts for

collaborators

Showing 2014Show all

3 papers · 1 filter

math.CO2014★ 8 cited

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.CO2014★ 16 cited

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…

cs.DM2014★ 7 cited

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}$ .

Better 3-coloring algorithms: excluding a triangle and a seven vertex path

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

4-coloring P6​-free graphs with no induced 5-cycles

4-coloring $P_{6}$ -free graphs with no induced 5-cycles