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 cs.CCShow 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.CC2013★ 23 cited

Improved Complexity Results on $k$ -Coloring $P_{t}$ -Free Graphs

Shenwei Huang

A graph is $H$ -free if it does not contain an induced subgraph isomorphic to $H$ . We denote by $P_{k}$ and $C_{k}$ the path and the cycle on $k$ vertices, respectively. In this paper,…

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

Improved Complexity Results on k-Coloring Pt​-Free Graphs

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

Improved Complexity Results on $k$ -Coloring $P_{t}$ -Free Graphs