Shenwei Huang

activity

20132026

most citedImproved Complexity Results on

k

-Coloring

P_{t}

-Free Graphs

23 citations · 59 across the 29 of their papers we have counts for

collaborators

Showing 2018Show all

5 papers · 1 filter

math.CO2018

An Optimal $χ$ -Bound for ( $P_{6}$ , diamond)-Free Graphs

Kathie Cameron, Shenwei Huang, Owen Merkel

Given two graphs $H_{1}$ and $H_{2}$ , a graph $G$ is $(H_{1}, H_{2})$ -free if it contains no induced subgraph isomorphic to $H_{1}$ or $H_{2}$ . Let $P_{t}$ be the path on $t$ vertices and $K_{t}$ b…

math.CO2018

List-three-coloring graphs with no induced $P_{6} + r P_{3}$

Maria Chudnovsky, Shenwei Huang, Sophie Spirkl +1

For an integer $r$ , the graph $P_{6} + r P_{3}$ has $r + 1$ components, one of which is a path on $6$ vertices, and each of the others is a path on $3$ vertices. In this paper we provide a…

math.CO2018

$(2 P_{2}, K_{4})$ -Free Graphs are 4-Colorable

Serge Gaspers, Shenwei Huang

In this paper, we show that every $(2 P_{2}, K_{4})$ -free graph is 4-colorable. The bound is attained by the five-wheel and the complement of the seven-cycle. This answers an open questi…

math.CO2018

Colouring Square-Free Graphs without Long Induced Paths

Serge Gaspers, Shenwei Huang, Daniël Paulusma

The complexity of {\sc Colouring} is fully understood for $H$ -free graphs, but there are still major complexity gaps if two induced subgraphs $H_{1}$ and $H_{2}$ are forbidden. Let $H_…

math.CO2018

The class of $(P_{7}, C_{4}, C_{5})$ -free graphs: decomposition, algorithms, and $χ$ -boundedness

Kathie Cameron, Shenwei Huang, Irena Penev +1

As usual, $P_{n}$ ( $n \geq 1$ ) denotes the path on $n$ vertices, and $C_{n}$ ( $n \geq 3$ ) denotes the cycle on $n$ vertices. For a family $H$ of graphs, we say that a graph $…

An Optimal χ-Bound for (P6​, diamond)-Free Graphs

List-three-coloring graphs with no induced P6​+rP3​

(2P2​,K4​)-Free Graphs are 4-Colorable

Colouring Square-Free Graphs without Long Induced Paths

The class of (P7​,C4​,C5​)-free graphs: decomposition, algorithms, and χ-boundedness

An Optimal $χ$ -Bound for ( $P_{6}$ , diamond)-Free Graphs

List-three-coloring graphs with no induced $P_{6} + r P_{3}$

$(2 P_{2}, K_{4})$ -Free Graphs are 4-Colorable

The class of $(P_{7}, C_{4}, C_{5})$ -free graphs: decomposition, algorithms, and $χ$ -boundedness