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 math.COShow all

22 papers · 1 filter

math.CO2026

Erdős-Hajnal conjecture beyond five-vertex graphs

Shenwei Huang, Yiao Ju, Yidong Zhou

In 1989, Erdős and Hajnal conjectured that for any graph $H$ , there is a constant $c = c (H) > 0$ such that every $n$ -vertex graph $G$ with no induced copies of $H$ contains a clique or…

math.CO2026

The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths

Shenwei Huang, Yidong Zhou, Yeonsu Chang

The class of even-hole-free graphs has been extensively studied on its own and on its relation to perfect graphs. In this paper, we study the $χ$ -boundedness of even-hole-free grap…

math.CO2025

3-Coloring $P_{t}$ -Free Graphs With Only One Prescribed Induced Odd Cycle Length

Yidong Zhou, Mingxian Zhong, Shenwei Huang

A graph is $P_{t}$ -free if it contains no induced subgraph isomorphic to a $t$ -vertex path. A graph is not bipartite if and only if it contains an induced subgraph isomorphic to a $k…

math.CO2025

Critical $(P_{5}, W_{4})$ -Free Graphs

Wen Xia, Jorik Jooken, Jan Goedgebeur +3

A graph $G$ is $k$ -vertex-critical if $χ (G) = k$ but $χ (G - v) < k$ for all $v \in V (G)$ . A graph is $(H_{1}, H_{2})$ -free if it contains no induced subgraph isomorphic to $H_{1}$ nor $H_{2}$ .…

math.CO2024

Some Results on Critical ( $P_{5}, H$ )-free Graphs

Wen Xia, Jorik Jooken, Jan Goedgebeur +1

Given two graphs $H_{1}$ and $H_{2}$ , a graph is $(H_{1}, H_{2})$ -free if it contains no induced subgraph isomorphic to $H_{1}$ nor $H_{2}$ . A graph $G$ is $k$ -vertex-critical if every proper i…

math.CO2023★ 1 cited

Critical $(P_{5}, d a r t)$ -Free Graphs

Wen Xia, Jorik Jooken, Jan Goedgebeur +1

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

math.CO2023

Near Optimal Colourability on Hereditary Graph Families

Yiao Ju, Shenwei Huang

In this paper, we initiate a systematic study on a new notion called near optimal colourability which is closely related to perfect graphs and the Lov{á}sz theta function. A graph…

math.CO2022

The optimal $χ$ -bound for $(P_{7}, C_{4}, C_{5})$ -free graphs

Shenwei Huang

In this paper, we give an optimal $χ$ -binding function for the class of $(P_{7}, C_{4}, C_{5})$ -free graphs. We show that every $(P_{7}, C_{4}, C_{5})$ -free graph $G$ has $χ(G)\le \lceil \frac{11}…

math.CO2022

Coloring ( $P_{5}$ , kite)-free graphs

Shenwei Huang, Yiao Ju, T. Karthick

Let $P_{n}$ and $K_{n}$ denote the induced path and complete graph on $n$ vertices, respectively. The {\em kite} is the graph obtained from a $P_{4}$ by adding a vertex and making it adj…

math.CO2021

Short proofs on $k$ -extendible graphs

Shenwei Huang, Yongtang Shi

In this note, we give short inductive proofs of two known results on $k$ -extendible graphs based on a property proved in [Qinglin Yu, A note on $n$ -extendable graphs. Journal of Gr…

math.CO2021★ 1 cited

Some Results on $k$ -Critical $P_{5}$ -Free Graphs

Qingqiong Cai, Jan Goedgebeur, Shenwei Huang

A graph $G$ is $k$ -vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$ . The study of $k$ -vertex-critical gra…

math.CO2021

Colouring graphs with no induced six-vertex path or diamond

Jan Goedgebeur, Shenwei Huang, Yiao Ju +1

The diamond is the graph obtained by removing an edge from the complete graph on 4 vertices. A graph is ( $P_{6}$ , diamond)-free if it contains no induced subgraph isomorphic to a six…

math.CO2020★ 1 cited

Some extremal results on the chromatic-stability index

Shenwei Huang, Sandi Klavžar, Hui Lei +2

The $χ$ -stability index $es_{χ} (G)$ of a graph $G$ is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of $G$ . In th…

math.CO2020★ 1 cited

$k$ -Critical Graphs in $P_{5}$ -Free Graphs

Kathie Cameron, Jan Goedgebeur, Shenwei Huang +1

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. A graph $G…

math.CO2019

The saturation number of $K_{3, 3}$

Shenwei Huang, Hui Lei, Yongtang Shi +1

A graph $G$ is called $F$ -saturated if $G$ does not contain $F$ as a subgraph (not necessarily induced) but the addition of any missing edge to $G$ creates a copy of $F$ . The satur…

math.CO2019★ 5 cited

On graphs with no induced five-vertex path or paraglider

Shenwei Huang, T. Karthick

Given two graphs $H_{1}$ and $H_{2}$ , a graph is $(H_{1}, H_{2})$ -free if it contains no induced subgraph isomorphic to $H_{1}$ or $H_{2}$ . For a positive integer $t$ , $P_{t}$ is the chordless…

math.CO2018

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

Kathie Cameron, Shenwei Huang, Owen Merkel

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

math.CO2017

Linearly $χ$ -Bounding $(P_{6}, C_{4})$ -Free Graphs

Serge Gaspers, Shenwei Huang

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

Erdős-Hajnal conjecture beyond five-vertex graphs

The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths

3-Coloring Pt​-Free Graphs With Only One Prescribed Induced Odd Cycle Length

Critical (P5​,W4​)-Free Graphs

Some Results on Critical (P5​,H)-free Graphs

Critical (P5​,dart)-Free Graphs

Near Optimal Colourability on Hereditary Graph Families

The optimal χ-bound for (P7​,C4​,C5​)-free graphs

Coloring (P5​, kite)-free graphs

Short proofs on k-extendible graphs

Some Results on k-Critical P5​-Free Graphs

Colouring graphs with no induced six-vertex path or diamond

Some extremal results on the chromatic-stability index

k-Critical Graphs in P5​-Free Graphs

The saturation number of K3,3​

On graphs with no induced five-vertex path or paraglider

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

Linearly χ-Bounding (P6​,C4​)-Free Graphs

3-Coloring $P_{t}$ -Free Graphs With Only One Prescribed Induced Odd Cycle Length

Critical $(P_{5}, W_{4})$ -Free Graphs

Some Results on Critical ( $P_{5}, H$ )-free Graphs

Critical $(P_{5}, d a r t)$ -Free Graphs

The optimal $χ$ -bound for $(P_{7}, C_{4}, C_{5})$ -free graphs

Coloring ( $P_{5}$ , kite)-free graphs

Short proofs on $k$ -extendible graphs

Some Results on $k$ -Critical $P_{5}$ -Free Graphs

$k$ -Critical Graphs in $P_{5}$ -Free Graphs

The saturation number of $K_{3, 3}$

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

Linearly $χ$ -Bounding $(P_{6}, C_{4})$ -Free Graphs