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 2014Show all

2 papers · 1 filter

cs.CC2014★ 8 cited

Narrowing the Complexity Gap for Colouring ( $C_{s}$ , $P_{t}$ )-Free Graphs

Shenwei Huang, Matthew Johnson, Daniël Paulusma

For a positive integer $k$ and graph $G = (V, E)$ , a $k$ -colouring of $G$ is a mapping $c : V \to {1, 2, \dots, k}$ such that $c (u) \neq = c (v)$ whenever $uv \in E$ . The $k$ -Colourin…

cs.DM2014

Bounding Clique-Width via Perfect Graphs

Konrad K. Dabrowski, Shenwei Huang, Daniël Paulusma

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}$ . We continue a recent study into the clique-width of $(H_1…

Narrowing the Complexity Gap for Colouring (Cs​,Pt​)-Free Graphs

Bounding Clique-Width via Perfect Graphs

Narrowing the Complexity Gap for Colouring ( $C_{s}$ , $P_{t}$ )-Free Graphs