Every graph with treewidth k admits a tree-decomposition of width <=14k+13 with each vertex in <=deg(v)+1 bags, plus a second decomposition of width <=3k-1 with average three bags per vertex.
17 Mihalis Yannakakis
3 Pith papers cite this work, alongside 4 external citations. Polarity classification is still indexing.
3
Pith papers citing it
4
external citations · external index
fields
math.CO 3verdicts
UNVERDICTED 3representative citing papers
Every n-vertex H-minor-free graph admits a 3-coloring with monochromatic components of size O_H(n^{4/9}).
Graphs of treewidth k satisfy α_c(G) ≥ c/(c+k+1)n with matching upper-bound constructions; the bound improves to c/(c+k)n when c≤2 or k=1 and to 5/9 n when c=3 and k=2.
citing papers explorer
-
Tree decompositions with small width, spread, order and degree
Every graph with treewidth k admits a tree-decomposition of width <=14k+13 with each vertex in <=deg(v)+1 bags, plus a second decomposition of width <=3k-1 with average three bags per vertex.
-
3-Colouring Graphs Excluding a Fixed Minor
Every n-vertex H-minor-free graph admits a 3-coloring with monochromatic components of size O_H(n^{4/9}).
-
Clustered independence and bounded treewidth
Graphs of treewidth k satisfy α_c(G) ≥ c/(c+k+1)n with matching upper-bound constructions; the bound improves to c/(c+k)n when c≤2 or k=1 and to 5/9 n when c=3 and k=2.