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 ...
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$. ...
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 ...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
bounded-degree × 17cc.complexity-theory × 8
graph-colouring × 6
boolean-functions × 5
graph-theory × 4
np-hardness × 4
graph-algorithms × 2
co.combinatorics × 2
approximation-hardness × 2
randomness × 2
planar-graphs × 2
fourier-analysis × 2
ds.algorithms × 1
reference-request × 1
counting-complexity × 1
graph-isomorphism × 1
tree × 1
treewidth × 1
set-cover × 1
algebraic-complexity × 1
arithmetic-circuits × 1
hypergraphs × 1
graph-minor × 1
sum-of-squares × 1
enumeration × 1