bandwidth

tags: vertex order

providers: ISGCI

Definition: Minimum over vertex labeling by distinct integers, maximum over edges, absolute difference of labels of edge’s endpoints.


Relations

OtherRelation fromRelation to
acyclic chromatic numberredexclusionupper bound
admissibilityredexclusionupper bound
arboricityredexclusionupper bound
average degreeredexclusionupper bound
average distancemagentaexclusionunknown to HOPS
bandwidthyellowequalequal
bipartiteblueunboundedexclusion
bipartite numbermagentaexclusionunknown to HOPS
bisection bandwidthredexclusionupper bound
blockblueunboundedexclusion
book thicknessredexclusionupper bound
boolean widthredexclusionupper bound
bounded componentsgrayunknown to HOPSunknown to HOPS
bounded expansionredexclusionupper bound
boxicityredexclusionupper bound
branch widthredexclusionupper bound
c-closureredexclusionupper bound
carving-widthorangeunknown to HOPSupper bound
chi-boundedredexclusionupper bound
chordalblueunboundedexclusion
chordalityredexclusionupper bound
chromatic numberredexclusionupper bound
clique cover numbermagentaexclusionunknown to HOPS
clique-tree-widthredexclusionupper bound
clique-widthredexclusionupper bound
clusterblueunboundedexclusion
co-clusterblueunboundedexclusion
cographblueunboundedexclusion
completeblueunboundedexclusion
connectedblueexclusionavoids
contraction complexityorangeunknown to HOPSupper bound
cutwidthorangeunknown to HOPSnon-tight bounds
cyclegreenupper boundexclusion
cyclesgrayunknown to HOPSunknown to HOPS
d-admissibilityredexclusionupper bound
d-path-freemagentaexclusionunknown to HOPS
degeneracyredexclusionupper bound
degree treewidthorangeunknown to HOPSupper bound
diametermagentaexclusionunknown to HOPS
diameter+max degreegrayunknown to HOPSunknown to HOPS
distance to bipartiteblueexclusionexclusion
distance to blockblueexclusionexclusion
distance to bounded componentsmagentaexclusionunknown to HOPS
distance to chordalblueexclusionexclusion
distance to clusterblueexclusionexclusion
distance to co-clusterblueexclusionexclusion
distance to cographblueexclusionexclusion
distance to completeblueexclusionexclusion
distance to edgelessblueexclusionexclusion
distance to forestblueexclusionexclusion
distance to intervalblueexclusionexclusion
distance to linear forestblueexclusionexclusion
distance to maximum degreeredexclusionupper bound
distance to outerplanarblueexclusionexclusion
distance to perfectblueexclusionexclusion
distance to planarblueexclusionexclusion
distance to starsblueexclusionexclusion
domatic numberredexclusionupper bound
domination numbermagentaexclusionunknown to HOPS
domino treewidthorangeunknown to HOPSupper bound
edge clique cover numbermagentaexclusionunknown to HOPS
edge connectivityredexclusionupper bound
edge-cut widthmagentaexclusionunknown to HOPS
edge-treewidthredexclusionupper bound
edgelesscyanunknown to HOPSavoids
excluded minormagentaexclusionunknown to HOPS
excluded planar minorgrayunknown to HOPSunknown to HOPS
excluded top-minorredexclusionupper bound
feedback edge setblueexclusionexclusion
feedback vertex setblueexclusionexclusion
flip-widthredexclusionupper bound
forestblueunboundedexclusion
genusblueexclusionexclusion
gridblueunboundedexclusion
h-indexredexclusionupper bound
intervalblueunboundedexclusion
iterated type partitionsmagentaexclusionunknown to HOPS
linear clique-widthredexclusionupper bound
linear forestcyanunknown to HOPSexclusion
linear NLC-widthredexclusionupper bound
linear rank-widthredexclusionupper bound
maximum cliqueredexclusionupper bound
maximum degreeredexclusionupper bound
maximum independent setmagentaexclusionunknown to HOPS
maximum induced matchingmagentaexclusionunknown to HOPS
maximum leaf numbergreenupper boundexclusion
maximum matchingblueexclusionexclusion
maximum matching on bipartite graphsblueexclusionexclusion
merge-widthredexclusionupper bound
mim-widthredexclusionupper bound
minimum degreeredexclusionupper bound
mm-widthredexclusionupper bound
modular-widthmagentaexclusionunknown to HOPS
module-widthredexclusionupper bound
monadically dependentredexclusionupper bound
monadically stableredexclusionupper bound
neighborhood diversitymagentaexclusionunknown to HOPS
NLC-widthredexclusionupper bound
NLCT-widthredexclusionupper bound
nowhere denseredexclusionupper bound
odd cycle transversalblueexclusionexclusion
outerplanarcyanunknown to HOPSexclusion
overlap treewidthredexclusionupper bound
pathcyanunknown to HOPSexclusion
pathwidthredexclusionupper bound
pathwidth+maxdegreeorangeunknown to HOPSupper bound
perfectblueunboundedexclusion
planarblueunboundedexclusion
radius-inf flip-widthredexclusionupper bound
radius-r flip-widthredexclusionupper bound
rank-widthredexclusionupper bound
series-parallelgrayunknown to HOPSunknown to HOPS
shrub-depthmagentaexclusionunknown to HOPS
sim-widthredexclusionupper bound
sizegreenupper boundexclusion
slim tree-cut widthredexclusionupper bound
sparse twin-widthredexclusionupper bound
starblueunboundedexclusion
starsblueunboundedexclusion
strong coloring numberredexclusionupper bound
strong d-coloring numberredexclusionupper bound
strong inf-coloring numberredexclusionupper bound
topological bandwidthorangeunknown to HOPSupper bound
treeblueunboundedexclusion
tree-cut widthredexclusionupper bound
tree-independence numberredexclusionupper bound
tree-partition-widthredexclusionupper bound
treebandwidthredexclusionupper bound
treedepthmagentaexclusionunknown to HOPS
treelengthmagentaexclusionunknown to HOPS
treespanorangeunknown to HOPSupper bound
treewidthredexclusionupper bound
twin-cover numberblueexclusionexclusion
twin-widthredexclusionupper bound
vertex connectivitymagentaexclusionunknown to HOPS
vertex coverblueexclusionexclusion
vertex integritymagentaexclusionunknown to HOPS
weak coloring numberredexclusionupper bound
weak d-coloring numberredexclusionupper bound
weak inf-coloring numbermagentaexclusionunknown to HOPS
weakly sparseredexclusionupper bound
weakly sparse and merge widthredexclusionupper bound

Results