path

Definitions:

an intersetcion of connected, and linear forest
Vertices can be ordered such that exactly those next to each other in the order are connected by an edge.

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	magenta■	exclusion	unknown to HOPS
bandwidth	magenta■	exclusion	unknown to HOPS
bipartite	red■	exclusion	upper bound
bipartite number	blue■	exclusion	unbounded
bisection bandwidth	magenta■	exclusion	unknown to HOPS
block	red■	exclusion	upper bound
book thickness	red■	exclusion	upper bound
boolean width	red■	exclusion	upper bound
bounded components	blue■	exclusion	unbounded
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	red■	exclusion	upper bound
chi-bounded	red■	exclusion	upper bound
chordal	red■	exclusion	upper bound
chordality	red■	exclusion	upper bound
chromatic number	red■	exclusion	upper bound
clique cover number	blue■	exclusion	unbounded
clique-tree-width	red■	exclusion	upper bound
clique-width	red■	exclusion	upper bound
cluster	blue■	exclusion	exclusion
co-cluster	blue■	exclusion	exclusion
cograph	blue■	exclusion	exclusion
complete	blue■	exclusion	exclusion
connected	red■	exclusion	upper bound
contraction complexity	red■	exclusion	upper bound
cutwidth	red■	exclusion	upper bound
cycle	gray■	unknown to HOPS	unknown to HOPS
cycles	magenta■	exclusion	unknown to HOPS
d-admissibility	red■	exclusion	upper bound
d-path-free	blue■	exclusion	unbounded
degeneracy	red■	exclusion	upper bound
degree treewidth	red■	exclusion	upper bound
diameter	blue■	exclusion	unbounded
diameter+max degree	blue■	exclusion	unbounded
distance to bipartite	red■	exclusion	upper bound
distance to block	red■	exclusion	upper bound
distance to bounded components	blue■	exclusion	unbounded
distance to chordal	red■	exclusion	upper bound
distance to cluster	blue■	exclusion	unbounded
distance to co-cluster	blue■	exclusion	unbounded
distance to cograph	blue■	exclusion	unbounded
distance to complete	blue■	exclusion	unbounded
distance to edgeless	blue■	exclusion	unbounded
distance to forest	red■	exclusion	upper bound
distance to interval	red■	exclusion	upper bound
distance to linear forest	red■	exclusion	upper bound
distance to maximum degree	red■	exclusion	upper bound
distance to outerplanar	red■	exclusion	upper bound
distance to perfect	red■	exclusion	upper bound
distance to planar	red■	exclusion	upper bound
distance to stars	blue■	exclusion	unbounded
domatic number	red■	exclusion	upper bound
domination number	blue■	exclusion	unbounded
domino treewidth	red■	exclusion	upper bound
edge clique cover number	blue■	exclusion	unbounded
edge connectivity	red■	exclusion	upper bound
edge-cut width	red■	exclusion	upper bound
edge-treewidth	red■	exclusion	upper bound
edgeless	blue■	exclusion	avoids
excluded minor	red■	exclusion	upper bound
excluded planar minor	gray■	unknown to HOPS	unknown to HOPS
excluded top-minor	red■	exclusion	upper bound
feedback edge set	red■	exclusion	upper bound
feedback vertex set	red■	exclusion	upper bound
flip-width	red■	exclusion	upper bound
forest	red■	exclusion	upper bound
genus	red■	exclusion	upper bound
grid	red■	exclusion	inclusion
h-index	red■	exclusion	upper bound
interval	red■	exclusion	upper bound
iterated type partitions	blue■	exclusion	unbounded
linear clique-width	red■	exclusion	upper bound
linear forest	red■	exclusion	upper bound
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	unbounded
maximum induced matching	blue■	exclusion	unbounded
maximum leaf number	magenta■	exclusion	unknown to HOPS
maximum matching	blue■	exclusion	unbounded
maximum matching on bipartite graphs	blue■	exclusion	unbounded
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	unbounded
module-width	red■	exclusion	upper bound
monadically dependent	red■	exclusion	upper bound
monadically stable	red■	exclusion	upper bound
neighborhood diversity	blue■	exclusion	unbounded
NLC-width	red■	exclusion	upper bound
NLCT-width	red■	exclusion	upper bound
nowhere dense	red■	exclusion	upper bound
odd cycle transversal	red■	exclusion	upper bound
outerplanar	gray■	unknown to HOPS	unknown to HOPS
overlap treewidth	red■	exclusion	upper bound
path	yellow■	equal	equal
pathwidth	red■	exclusion	upper bound
pathwidth+maxdegree	red■	exclusion	upper bound
perfect	red■	exclusion	upper bound
planar	red■	exclusion	upper bound
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	blue■	exclusion	unbounded
slim tree-cut width	red■	exclusion	upper bound
sparse twin-width	red■	exclusion	upper bound
star	blue■	exclusion	exclusion
stars	blue■	exclusion	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	magenta■	exclusion	unknown to HOPS
tree	red■	exclusion	inclusion
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	unbounded
treelength	magenta■	exclusion	unknown to HOPS
treespan	red■	exclusion	upper bound
treewidth	red■	exclusion	upper bound
twin-cover number	blue■	exclusion	unbounded
twin-width	red■	exclusion	upper bound
vertex connectivity	magenta■	exclusion	unknown to HOPS
vertex cover	blue■	exclusion	unbounded
vertex integrity	blue■	exclusion	unbounded
weak coloring number	red■	exclusion	upper bound
weak d-coloring number	red■	exclusion	upper bound
weak inf-coloring number	blue■	exclusion	unbounded
weakly sparse	red■	exclusion	upper bound
weakly sparse and merge width	red■	exclusion	upper bound

Results

2022 Expanding the Graph Parameter Hierarchy by Tran
- page 24 : graph class path is not constant modular-width – The Modular-width of a path $P$ with length $n > 3$ is $n$.
- page 26 : graph class path is not constant neighborhood diversity – The Neighborhood Diversity of a Path $P$ with length $n > 3$ is $n$.
2010 Comparing 17 graph parameters by Sasák
- page 30 : path upper bounds carving-width by a constant – … path with carving-width 2.
unknown source
- graph class path is not constant treedepth
- graph class path is not constant distance to cluster – trivially
- graph class path is not constant diameter – trivially
- graph class path is not constant maximum matching
assumed
- path upper bounds connected by a constant – by definition
- path upper bounds linear forest by a constant – by definition
- graph class path has contained in tree
- graph class tree does not have contained in path
- graph class path has contained in grid
- graph class grid does not have contained in path
- path is equivalent to path – assumed