17 votes
Accepted

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

The answer is no: the 3-coloring problem can be solved in linear time on graphs of maximal degree 3 or less, by application of Brooks' theorem. I wasted some time figuring this out, so I thought I'd ...
a3nm's user avatar
  • 8,896
14 votes
Accepted

Finding subgraphs with high treewidth and constant degree

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers. We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$. ...
Chandra Chekuri's user avatar
1 vote

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

Thanks to Prof. @Yixin Cao's construction of the reduction, I think I have found a way to show that Planar-DFVS remains $\textsf{NP}$-hard when $(\Delta_{in}, \Delta_{out}) = (2, 2)$. We use the ...
Blanco's user avatar
  • 421
1 vote

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

Warning: this does not completely solve your question because the gadget is not planar. But since I could not find a proof of this, I think it might be worth posting. Speckenmeyer proved that the ...
Yixin Cao's user avatar
  • 2,560
1 vote

Finding subgraphs with high treewidth and constant degree

In the case of pathwidth, reposting here a comment made to me by email by Benjamin Rossman back in 2020 (see also the comments to the answer https://cstheory.stackexchange.com/a/38943): Every graph G ...
a3nm's user avatar
  • 8,896

Only top scored, non community-wiki answers of a minimum length are eligible