maximum matching

functionally equivalent to: distance to edgeless, vertex cover

providers: ISGCI

Definition: The size of a maximum independent edge set.


Relations

OtherRelation fromRelation to
acyclic chromatic numberredexclusionupper bound
admissibilityredexclusionupper bound
arboricityredexclusionupper bound
average degreeredexclusionupper bound
average distanceredexclusionupper bound
bandwidthblueexclusionexclusion
bipartiteblueunboundedexclusion
bipartite numberblueexclusionexclusion
bisection bandwidthblueexclusionexclusion
blockblueunboundedexclusion
book thicknessredexclusionupper bound
boolean widthredexclusionupper bound
bounded componentsblueexclusionexclusion
bounded expansionredexclusionupper bound
boxicityredexclusionupper bound
branch widthredexclusionupper bound
c-closureblueexclusionexclusion
carving-widthblueexclusionexclusion
chi-boundedredexclusionupper bound
chordalblueunboundedexclusion
chordalityredexclusionupper bound
chromatic numberredexclusionupper bound
clique cover numberblueexclusionexclusion
clique-tree-widthredexclusionupper bound
clique-widthredexclusionupper bound
clusterblueunboundedexclusion
co-clusterblueunboundedexclusion
cographblueunboundedexclusion
completeblueunboundedexclusion
connectedblueexclusionavoids
contraction complexityblueexclusionexclusion
cutwidthblueexclusionexclusion
cyclecyanunknown to HOPSexclusion
cyclesblueunboundedexclusion
d-admissibilityredexclusionupper bound
d-path-freeredexclusionupper bound
degeneracyredexclusionupper bound
degree treewidthblueexclusionexclusion
diameterredexclusionupper bound
diameter+max degreeblueexclusionexclusion
distance to bipartiteredexclusionupper bound
distance to blockredexclusionupper bound
distance to bounded componentsredexclusionupper bound
distance to chordalredexclusionupper bound
distance to clusterredexclusionupper bound
distance to co-clusterredexclusionupper bound
distance to cographredexclusionupper bound
distance to completeblueexclusionexclusion
distance to edgelessyellowtight boundsupper bound
distance to forestredexclusionupper bound
distance to intervalredexclusionupper bound
distance to linear forestredexclusionupper bound
distance to maximum degreeredexclusionupper bound
distance to outerplanarredexclusionupper bound
distance to perfectredexclusionupper bound
distance to planarredexclusionupper bound
distance to starsredexclusionupper bound
domatic numberredexclusionupper bound
domination numberblueexclusionexclusion
domino treewidthblueexclusionexclusion
edge clique cover numberblueexclusionexclusion
edge connectivityredexclusionupper bound
edge-cut widthmagentaexclusionunknown to HOPS
edge-treewidthmagentaexclusionunknown to HOPS
edgelessgreenupper boundavoids
excluded minormagentaexclusionunknown to HOPS
excluded planar minorgrayunknown to HOPSunknown to HOPS
excluded top-minorredexclusionupper bound
feedback edge setblueexclusionexclusion
feedback vertex setredexclusionupper bound
flip-widthredexclusionupper bound
forestblueunboundedexclusion
genusblueexclusionexclusion
gridblueunboundedexclusion
h-indexredexclusionupper bound
intervalblueunboundedexclusion
iterated type partitionsredexclusionupper bound
linear clique-widthredexclusionupper bound
linear forestblueunboundedexclusion
linear NLC-widthredexclusionupper bound
linear rank-widthredexclusionupper bound
maximum cliqueredexclusionupper bound
maximum degreeblueexclusionexclusion
maximum independent setblueexclusionexclusion
maximum induced matchingredexclusionupper bound
maximum leaf numbercyanunknown to HOPSexclusion
maximum matchingyellowequalequal
maximum matching on bipartite graphsgreenupper boundexclusion
merge-widthredexclusionupper bound
mim-widthredexclusionupper bound
minimum degreeredexclusionupper bound
mm-widthredexclusionupper bound
modular-widthredexclusionupper bound
module-widthredexclusionupper bound
monadically dependentredexclusionupper bound
monadically stableredexclusionupper bound
neighborhood diversityredexclusionupper bound
NLC-widthredexclusionupper bound
NLCT-widthredexclusionupper bound
nowhere denseredexclusionupper bound
odd cycle transversalredexclusionupper bound
outerplanarcyanunknown to HOPSexclusion
overlap treewidthmagentaexclusionunknown to HOPS
pathblueunboundedexclusion
pathwidthredexclusionupper bound
pathwidth+maxdegreeblueexclusionexclusion
perfectblueunboundedexclusion
planarblueunboundedexclusion
radius-inf flip-widthredexclusionupper bound
radius-r flip-widthredexclusionupper bound
rank-widthredexclusionupper bound
series-parallelgrayunknown to HOPSunknown to HOPS
shrub-depthredexclusionupper bound
sim-widthredexclusionupper bound
sizegreenupper boundexclusion
slim tree-cut widthmagentaexclusionunknown to HOPS
sparse twin-widthredexclusionupper bound
stargreenupper boundexclusion
starsblueunboundedexclusion
strong coloring numberredexclusionupper bound
strong d-coloring numberredexclusionupper bound
strong inf-coloring numberredexclusionupper bound
topological bandwidthblueexclusionexclusion
treeblueunboundedexclusion
tree-cut widthmagentaexclusionunknown to HOPS
tree-independence numberredexclusionupper bound
tree-partition-widthmagentaexclusionunknown to HOPS
treebandwidthmagentaexclusionunknown to HOPS
treedepthredexclusionupper bound
treelengthredexclusionupper bound
treespanblueexclusionexclusion
treewidthredexclusionupper bound
twin-cover numberredexclusionupper bound
twin-widthredexclusionupper bound
vertex connectivitygrayunknown to HOPSunknown to HOPS
vertex coveryellowtight boundsupper bound
vertex integrityredexclusionupper bound
weak coloring numberredexclusionupper bound
weak d-coloring numberredexclusionupper bound
weak inf-coloring numberredexclusionupper bound
weakly sparseredexclusionupper bound
weakly sparse and merge widthredexclusionupper bound

Results