cutwidth

functionally equivalent to: pathwidth+maxdegree

providers: ISGCI

Definition: Minimum over vertex orders, maximum over positions (between vertices), number of edges that have endpoints on different sides of the position.

Relations

Other		Relation from	Relation to
acyclic chromatic number	red■	exclusion	upper bound
admissibility	red■	exclusion	upper bound
arboricity	red■	exclusion	upper bound
average degree	red■	exclusion	upper bound
average distance	blue■	exclusion	exclusion
bandwidth	lime■	non-tight bounds	unknown to HOPS
bipartite	blue■	unbounded	exclusion
bipartite number	blue■	exclusion	exclusion
bisection bandwidth	magenta■	exclusion	unknown to HOPS
block	blue■	unbounded	exclusion
book thickness	red■	exclusion	upper bound
boolean width	red■	exclusion	upper bound
bounded components	green■	upper bound	exclusion
bounded expansion	red■	exclusion	upper bound
boxicity	red■	exclusion	upper bound
branch width	red■	exclusion	upper bound
c-closure	red■	exclusion	upper bound
carving-width	orange■	unknown to HOPS	upper bound
chi-bounded	red■	exclusion	upper bound
chordal	blue■	unbounded	exclusion
chordality	red■	exclusion	upper bound
chromatic number	red■	exclusion	upper bound
clique cover number	blue■	exclusion	exclusion
clique-tree-width	red■	exclusion	upper bound
clique-width	red■	exclusion	upper bound
cluster	blue■	unbounded	exclusion
co-cluster	blue■	unbounded	exclusion
cograph	blue■	unbounded	exclusion
complete	blue■	unbounded	exclusion
connected	blue■	exclusion	avoids
contraction complexity	orange■	unknown to HOPS	upper bound
cutwidth	yellow■	equal	equal
cycle	green■	upper bound	exclusion
cycles	green■	upper bound	exclusion
d-admissibility	red■	exclusion	upper bound
d-path-free	blue■	exclusion	exclusion
degeneracy	red■	exclusion	upper bound
degree treewidth	orange■	unknown to HOPS	upper bound
diameter	blue■	exclusion	exclusion
diameter+max degree	green■	upper bound	exclusion
distance to bipartite	blue■	exclusion	exclusion
distance to block	blue■	exclusion	exclusion
distance to bounded components	blue■	exclusion	exclusion
distance to chordal	blue■	exclusion	exclusion
distance to cluster	blue■	exclusion	exclusion
distance to co-cluster	blue■	exclusion	exclusion
distance to cograph	blue■	exclusion	exclusion
distance to complete	blue■	exclusion	exclusion
distance to edgeless	blue■	exclusion	exclusion
distance to forest	blue■	exclusion	exclusion
distance to interval	blue■	exclusion	exclusion
distance to linear forest	blue■	exclusion	exclusion
distance to maximum degree	red■	exclusion	upper bound
distance to outerplanar	blue■	exclusion	exclusion
distance to perfect	blue■	exclusion	exclusion
distance to planar	blue■	exclusion	exclusion
distance to stars	blue■	exclusion	exclusion
domatic number	red■	exclusion	upper bound
domination number	blue■	exclusion	exclusion
domino treewidth	orange■	unknown to HOPS	upper bound
edge clique cover number	blue■	exclusion	exclusion
edge connectivity	red■	exclusion	upper bound
edge-cut width	magenta■	exclusion	unknown to HOPS
edge-treewidth	red■	exclusion	upper bound
edgeless	green■	upper bound	avoids
excluded minor	magenta■	exclusion	unknown to HOPS
excluded planar minor	gray■	unknown to HOPS	unknown to HOPS
excluded top-minor	red■	exclusion	upper bound
feedback edge set	blue■	exclusion	exclusion
feedback vertex set	blue■	exclusion	exclusion
flip-width	red■	exclusion	upper bound
forest	blue■	unbounded	exclusion
genus	blue■	exclusion	exclusion
grid	blue■	unbounded	exclusion
h-index	red■	exclusion	upper bound
interval	blue■	unbounded	exclusion
iterated type partitions	blue■	exclusion	exclusion
linear clique-width	red■	exclusion	upper bound
linear forest	green■	upper bound	exclusion
linear NLC-width	red■	exclusion	upper bound
linear rank-width	red■	exclusion	upper bound
maximum clique	red■	exclusion	upper bound
maximum degree	red■	exclusion	upper bound
maximum independent set	blue■	exclusion	exclusion
maximum induced matching	blue■	exclusion	exclusion
maximum leaf number	green■	upper bound	exclusion
maximum matching	blue■	exclusion	exclusion
maximum matching on bipartite graphs	blue■	exclusion	exclusion
merge-width	red■	exclusion	upper bound
mim-width	red■	exclusion	upper bound
minimum degree	red■	exclusion	upper bound
mm-width	red■	exclusion	upper bound
modular-width	blue■	exclusion	exclusion
module-width	red■	exclusion	upper bound
monadically dependent	red■	exclusion	upper bound
monadically stable	red■	exclusion	upper bound
neighborhood diversity	blue■	exclusion	exclusion
NLC-width	red■	exclusion	upper bound
NLCT-width	red■	exclusion	upper bound
nowhere dense	red■	exclusion	upper bound
odd cycle transversal	blue■	exclusion	exclusion
outerplanar	cyan■	unknown to HOPS	exclusion
overlap treewidth	red■	exclusion	upper bound
path	green■	upper bound	exclusion
pathwidth	red■	exclusion	upper bound
pathwidth+maxdegree	yellow■	upper bound	upper bound
perfect	blue■	unbounded	exclusion
planar	blue■	unbounded	exclusion
radius-inf flip-width	red■	exclusion	upper bound
radius-r flip-width	red■	exclusion	upper bound
rank-width	red■	exclusion	upper bound
series-parallel	gray■	unknown to HOPS	unknown to HOPS
shrub-depth	magenta■	exclusion	unknown to HOPS
sim-width	red■	exclusion	upper bound
size	green■	upper bound	exclusion
slim tree-cut width	red■	exclusion	upper bound
sparse twin-width	red■	exclusion	upper bound
star	blue■	unbounded	exclusion
stars	blue■	unbounded	exclusion
strong coloring number	red■	exclusion	upper bound
strong d-coloring number	red■	exclusion	upper bound
strong inf-coloring number	red■	exclusion	upper bound
topological bandwidth	gray■	unknown to HOPS	unknown to HOPS
tree	blue■	unbounded	exclusion
tree-cut width	red■	exclusion	upper bound
tree-independence number	red■	exclusion	upper bound
tree-partition-width	red■	exclusion	upper bound
treebandwidth	red■	exclusion	upper bound
treedepth	blue■	exclusion	exclusion
treelength	magenta■	exclusion	unknown to HOPS
treespan	orange■	unknown to HOPS	upper bound
treewidth	red■	exclusion	upper bound
twin-cover number	blue■	exclusion	exclusion
twin-width	red■	exclusion	upper bound
vertex connectivity	magenta■	exclusion	unknown to HOPS
vertex cover	blue■	exclusion	exclusion
vertex integrity	blue■	exclusion	exclusion
weak coloring number	red■	exclusion	upper bound
weak d-coloring number	red■	exclusion	upper bound
weak inf-coloring number	blue■	exclusion	exclusion
weakly sparse	red■	exclusion	upper bound
weakly sparse and merge width	red■	exclusion	upper bound

Results

2010 Comparing 17 graph parameters by Sasák
- page 28 : cutwidth upper bounds maximum degree by a linear function – Lemma 2.18. For any graph $G$ and any vertex $v \in V(G), cutw(g) \ge \lceil \frac{deg(v)}2 \rceil$.
- page 38 : cutwidth upper bounds carving-width by a linear function – Theorem 4.3 (carw $\prec$ cutw) Carving-width is bounded by cut-width.
1998 A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
- page 22 : cutwidth – Let $G=(V,E)$ be a graph, and let $f\colon V\to {1,2,\dots,n}$ be a linear ordering of $G$. … 2. The \emph{cutwidth} of $f$ is $\max_{1\le i\le n} |{(u,v)\in E \mid f(u) \le i < f(v) }|$. … [cutwidth] of a graph $G$ is the minimum [cutwidth] … over all possible linear orderings of $G$.
- page 24 : cutwidth upper bounds pathwidth by a linear function – Theorem 47. For every graph $G$, the pathwidth of $G$ is at most the cutwidth of $G$.
- page 24 : pathwidth+maxdegree upper bounds cutwidth by a linear function – Theorem 49.
- page 24 : cutwidth upper bounds pathwidth+maxdegree by a linear function – Theorem 49.
assumed
- cutwidth is equivalent to cutwidth – assumed
unknown source
- bandwidth upper bounds cutwidth by a linear function and lower bounds it by a polynomial function – Any bandwidth bound cutwidth quadratically. An example where this happens is $(P_n)^k$ which has bandwidth $k$ and cutwidth $O(k^2)$; both seem to be optimal.
- bounded components upper bounds cutwidth by a linear function – By greedily placing one component after another.