pathwidth+maxdegree

tags: linear variant

equivalent to: pathwidth+maxdegree, cutwidth


Relations

OtherRelation fromRelation to
acyclic chromatic numberexclusionupper bound
arboricityexclusionupper bound
average degreeexclusionupper bound
average distanceexclusionexclusion
bandwidthupper boundunknown to HOPS
bipartiteunboundedexclusion
bipartite numberexclusionunknown to HOPS
bisection bandwidthexclusionunknown to HOPS
blockunboundedexclusion
book thicknessexclusionupper bound
boolean widthexclusionupper bound
bounded componentsupper boundexclusion
boxicityexclusionupper bound
branch widthexclusionupper bound
c-closureexclusionupper bound
carving-widthunknown to HOPSupper bound
chordalunboundedexclusion
chordalityexclusionupper bound
chromatic numberexclusionupper bound
clique cover numberexclusionexclusion
clique-tree-widthexclusionupper bound
clique-widthexclusionupper bound
clusterunboundedexclusion
co-clusterunboundedexclusion
cographunboundedexclusion
completeunboundedexclusion
connectedunboundedunknown to HOPS
cutwidthupper boundupper bound
cycleconstantexclusion
cyclesconstantexclusion
d-path-freeexclusionexclusion
degeneracyexclusionupper bound
degree treewidthunknown to HOPSupper bound
diameterexclusionexclusion
diameter+max degreeupper boundexclusion
disjoint cyclesunboundedexclusion
distance to bipartiteexclusionexclusion
distance to blockexclusionexclusion
distance to bounded componentsexclusionexclusion
distance to chordalexclusionexclusion
distance to clusterexclusionexclusion
distance to co-clusterexclusionexclusion
distance to cographexclusionexclusion
distance to completeexclusionexclusion
distance to edgelessexclusionexclusion
distance to forestexclusionexclusion
distance to intervalexclusionexclusion
distance to linear forestexclusionexclusion
distance to maximum degreeexclusionupper bound
distance to outerplanarexclusionexclusion
distance to perfectexclusionexclusion
distance to planarexclusionexclusion
distance to starsexclusionexclusion
domatic numberexclusionupper bound
domination numberexclusionexclusion
edge clique cover numberexclusionexclusion
edge connectivityexclusionupper bound
edgelessconstantexclusion
feedback edge setexclusionexclusion
feedback vertex setexclusionexclusion
forestunboundedexclusion
genusexclusionexclusion
girthexclusionexclusion
gridunboundedexclusion
h-indexexclusionupper bound
inf-flip-widthexclusionupper bound
intervalunboundedexclusion
iterated type partitionsexclusionexclusion
linear clique-widthexclusionupper bound
linear forestconstantexclusion
linear NLC-widthexclusionupper bound
linear rank-widthexclusionupper bound
maximum cliqueexclusionupper bound
maximum degreeexclusionupper bound
maximum independent setexclusionexclusion
maximum induced matchingexclusionexclusion
maximum leaf numberupper boundexclusion
maximum matchingexclusionexclusion
maximum matching on bipartite graphsexclusionexclusion
mim-widthexclusionupper bound
minimum degreeexclusionupper bound
mm-widthexclusionupper bound
modular-widthexclusionexclusion
module-widthexclusionupper bound
neighborhood diversityexclusionexclusion
NLC-widthexclusionupper bound
NLCT-widthexclusionupper bound
odd cycle transversalexclusionexclusion
outerplanarunboundedexclusion
pathconstantexclusion
pathwidthexclusionupper bound
perfectunboundedexclusion
planarunboundedexclusion
radius-r flip-widthexclusionupper bound
rank-widthexclusionupper bound
shrub-depthexclusionunknown to HOPS
sim-widthexclusionupper bound
starunboundedexclusion
starsunboundedexclusion
topological bandwidthunknown to HOPSunknown to HOPS
treeunboundedexclusion
tree-independence numberexclusionupper bound
treedepthexclusionexclusion
treelengthexclusionunknown to HOPS
treewidthexclusionupper bound
twin-cover numberexclusionexclusion
twin-widthexclusionupper bound
vertex connectivityexclusionunknown to HOPS
vertex coverexclusionexclusion
vertex integrityexclusionexclusion

Results