distance to bipartite

functionally equivalent to: odd cycle transversal

Definition: Minimum number of vertices removed to make the graph into bipartite


Relations

OtherRelation fromRelation to
acyclic chromatic numberblueexclusionexclusion
admissibilityblueexclusionexclusion
arboricityblueexclusionexclusion
average degreeblueexclusionexclusion
average distanceblueexclusionexclusion
bandwidthblueexclusionexclusion
bipartitegreenupper boundexclusion
bipartite numberblueexclusionexclusion
bisection bandwidthblueexclusionexclusion
blockblueunboundedexclusion
book thicknessblueexclusionexclusion
boolean widthblueexclusionexclusion
bounded componentsblueexclusionexclusion
bounded expansionblueexclusionavoids
boxicityblueexclusionexclusion
branch widthblueexclusionexclusion
c-closureblueexclusionexclusion
carving-widthblueexclusionexclusion
chi-boundedmagentaexclusionunknown to HOPS
chordalblueunboundedexclusion
chordalityredexclusionupper bound
chromatic numberredexclusionupper bound
clique cover numberblueexclusionexclusion
clique-tree-widthblueexclusionexclusion
clique-widthblueexclusionexclusion
clusterblueunboundedexclusion
co-clusterblueunboundedexclusion
cographblueunboundedexclusion
completeblueunboundedexclusion
connectedblueexclusionavoids
contraction complexityblueexclusionexclusion
cutwidthblueexclusionexclusion
cyclegreenupper boundexclusion
cyclesblueunboundedexclusion
d-admissibilitymagentaexclusionunknown to HOPS
d-path-freeblueexclusionexclusion
degeneracyblueexclusionexclusion
degree treewidthblueexclusionexclusion
diameterblueexclusionexclusion
diameter+max degreeblueexclusionexclusion
distance to bipartiteyellowequalequal
distance to blockblueexclusionexclusion
distance to bounded componentsblueexclusionexclusion
distance to chordalblueexclusionexclusion
distance to clusterblueexclusionexclusion
distance to co-clusterblueexclusionexclusion
distance to cographblueexclusionexclusion
distance to completeblueexclusionexclusion
distance to edgelessgreenupper boundexclusion
distance to forestgreenupper boundexclusion
distance to intervalblueexclusionexclusion
distance to linear forestgreenupper boundexclusion
distance to maximum degreeblueexclusionexclusion
distance to outerplanarblueexclusionexclusion
distance to perfectredexclusionupper bound
distance to planarblueexclusionexclusion
distance to starsgreenupper boundexclusion
domatic numberblueexclusionexclusion
domination numberblueexclusionexclusion
domino treewidthblueexclusionexclusion
edge clique cover numberblueexclusionexclusion
edge connectivityblueexclusionexclusion
edge-cut widthcyanunknown to HOPSexclusion
edge-treewidthblueexclusionexclusion
edgelessgreenupper boundavoids
excluded minorblueexclusionavoids
excluded planar minorcyanunknown to HOPSavoids
excluded top-minorblueexclusionavoids
feedback edge setgreenupper boundexclusion
feedback vertex setgreenupper boundexclusion
flip-widthmagentaexclusionunknown to HOPS
forestgreenupper boundexclusion
genusblueexclusionexclusion
gridgreenupper boundexclusion
h-indexblueexclusionexclusion
intervalblueunboundedexclusion
iterated type partitionsblueexclusionexclusion
linear clique-widthblueexclusionexclusion
linear forestgreenupper boundexclusion
linear NLC-widthblueexclusionexclusion
linear rank-widthblueexclusionexclusion
maximum cliqueredexclusionupper bound
maximum degreeblueexclusionexclusion
maximum independent setblueexclusionexclusion
maximum induced matchingblueexclusionexclusion
maximum leaf numbergreenupper boundexclusion
maximum matchinggreenupper boundexclusion
maximum matching on bipartite graphsgreenupper boundexclusion
merge-widthmagentaexclusionunknown to HOPS
mim-widthmagentaexclusionunknown to HOPS
minimum degreeblueexclusionexclusion
mm-widthblueexclusionexclusion
modular-widthblueexclusionexclusion
module-widthblueexclusionexclusion
monadically dependentmagentaexclusionunknown to HOPS
monadically stablemagentaexclusionunknown to HOPS
neighborhood diversityblueexclusionexclusion
NLC-widthblueexclusionexclusion
NLCT-widthblueexclusionexclusion
nowhere densemagentaexclusionunknown to HOPS
odd cycle transversalyellowequalequal
outerplanarcyanunknown to HOPSexclusion
overlap treewidthblueexclusionexclusion
pathgreenupper boundexclusion
pathwidthblueexclusionexclusion
pathwidth+maxdegreeblueexclusionexclusion
perfectblueunboundedexclusion
planarblueunboundedexclusion
radius-inf flip-widthblueexclusionexclusion
radius-r flip-widthmagentaexclusionunknown to HOPS
rank-widthblueexclusionexclusion
series-parallelgrayunknown to HOPSunknown to HOPS
shrub-depthblueexclusionexclusion
sim-widthmagentaexclusionunknown to HOPS
sizegreenupper boundexclusion
slim tree-cut widthblueexclusionexclusion
sparse twin-widthblueexclusionexclusion
stargreenupper boundexclusion
starsgreenupper boundexclusion
strong coloring numberblueexclusionexclusion
strong d-coloring numbermagentaexclusionunknown to HOPS
strong inf-coloring numberblueexclusionexclusion
topological bandwidthblueexclusionexclusion
treegreenupper boundexclusion
tree-cut widthblueexclusionexclusion
tree-independence numbermagentaexclusionunknown to HOPS
tree-partition-widthblueexclusionexclusion
treebandwidthblueexclusionexclusion
treedepthblueexclusionexclusion
treelengthmagentaexclusionunknown to HOPS
treespanblueexclusionexclusion
treewidthblueexclusionexclusion
twin-cover numberblueexclusionexclusion
twin-widthblueexclusionexclusion
vertex connectivitygrayunknown to HOPSunknown to HOPS
vertex covergreenupper boundexclusion
vertex integrityblueexclusionexclusion
weak coloring numberblueexclusionexclusion
weak d-coloring numbermagentaexclusionunknown to HOPS
weak inf-coloring numberblueexclusionexclusion
weakly sparsemagentaexclusionunknown to HOPS
weakly sparse and merge widthblueexclusionexclusion

Results