bipartite number
functionally equivalent to: maximum independent set
Definition: Bipartite number of $G$ is the maximum order of an induced bipartite subgraph.
Relations
Other | Relation from | Relation to | |
---|---|---|---|
acyclic chromatic number | ■ | exclusion | exclusion |
admissibility | ■ | exclusion | exclusion |
arboricity | ■ | exclusion | exclusion |
average degree | ■ | exclusion | exclusion |
average distance | ■ | exclusion | upper bound |
bandwidth | ■ | unknown to HOPS | exclusion |
bipartite | ■ | unbounded | exclusion |
bipartite number | ■ | equal | equal |
bisection bandwidth | ■ | unknown to HOPS | exclusion |
block | ■ | unbounded | exclusion |
book thickness | ■ | exclusion | exclusion |
boolean width | ■ | exclusion | exclusion |
bounded components | ■ | exclusion | exclusion |
bounded expansion | ■ | exclusion | avoids |
boxicity | ■ | exclusion | exclusion |
branch width | ■ | exclusion | exclusion |
c-closure | ■ | exclusion | exclusion |
carving-width | ■ | exclusion | exclusion |
chi-bounded | ■ | exclusion | unknown to HOPS |
chordal | ■ | unbounded | exclusion |
chordality | ■ | exclusion | exclusion |
chromatic number | ■ | exclusion | exclusion |
clique cover number | ■ | upper bound | exclusion |
clique-tree-width | ■ | exclusion | exclusion |
clique-width | ■ | exclusion | exclusion |
cluster | ■ | unbounded | exclusion |
co-cluster | ■ | unbounded | exclusion |
cograph | ■ | unbounded | exclusion |
complete | ■ | upper bound | exclusion |
connected | ■ | exclusion | avoids |
contraction complexity | ■ | exclusion | exclusion |
cutwidth | ■ | exclusion | exclusion |
cycle | ■ | unknown to HOPS | exclusion |
cycles | ■ | unknown to HOPS | exclusion |
d-admissibility | ■ | exclusion | unknown to HOPS |
d-path-free | ■ | exclusion | exclusion |
degeneracy | ■ | exclusion | exclusion |
degree treewidth | ■ | exclusion | exclusion |
diameter | ■ | exclusion | upper bound |
diameter+max degree | ■ | exclusion | exclusion |
distance to bipartite | ■ | exclusion | exclusion |
distance to block | ■ | exclusion | exclusion |
distance to bounded components | ■ | exclusion | exclusion |
distance to chordal | ■ | exclusion | exclusion |
distance to cluster | ■ | exclusion | exclusion |
distance to co-cluster | ■ | exclusion | exclusion |
distance to cograph | ■ | exclusion | exclusion |
distance to complete | ■ | upper bound | exclusion |
distance to edgeless | ■ | exclusion | exclusion |
distance to forest | ■ | exclusion | exclusion |
distance to interval | ■ | exclusion | exclusion |
distance to linear forest | ■ | exclusion | exclusion |
distance to maximum degree | ■ | exclusion | exclusion |
distance to outerplanar | ■ | exclusion | exclusion |
distance to perfect | ■ | exclusion | exclusion |
distance to planar | ■ | exclusion | exclusion |
distance to stars | ■ | exclusion | exclusion |
domatic number | ■ | exclusion | exclusion |
domination number | ■ | exclusion | upper bound |
domino treewidth | ■ | exclusion | exclusion |
edge clique cover number | ■ | exclusion | exclusion |
edge connectivity | ■ | exclusion | exclusion |
edge-cut width | ■ | exclusion | exclusion |
edge-treewidth | ■ | exclusion | exclusion |
edgeless | ■ | exclusion | avoids |
excluded minor | ■ | exclusion | avoids |
excluded planar minor | ■ | unknown to HOPS | avoids |
excluded top-minor | ■ | exclusion | avoids |
feedback edge set | ■ | exclusion | exclusion |
feedback vertex set | ■ | exclusion | exclusion |
flip-width | ■ | exclusion | unknown to HOPS |
forest | ■ | unbounded | exclusion |
genus | ■ | exclusion | exclusion |
grid | ■ | unbounded | exclusion |
h-index | ■ | exclusion | exclusion |
interval | ■ | unbounded | exclusion |
iterated type partitions | ■ | exclusion | exclusion |
linear clique-width | ■ | exclusion | exclusion |
linear forest | ■ | unbounded | exclusion |
linear NLC-width | ■ | exclusion | exclusion |
linear rank-width | ■ | exclusion | exclusion |
maximum clique | ■ | exclusion | exclusion |
maximum degree | ■ | exclusion | exclusion |
maximum independent set | ■ | upper bound | upper bound |
maximum induced matching | ■ | exclusion | upper bound |
maximum leaf number | ■ | unknown to HOPS | exclusion |
maximum matching | ■ | exclusion | exclusion |
maximum matching on bipartite graphs | ■ | exclusion | exclusion |
merge-width | ■ | exclusion | unknown to HOPS |
mim-width | ■ | exclusion | unknown to HOPS |
minimum degree | ■ | exclusion | exclusion |
mm-width | ■ | exclusion | exclusion |
modular-width | ■ | exclusion | exclusion |
module-width | ■ | exclusion | exclusion |
monadically dependent | ■ | exclusion | unknown to HOPS |
monadically stable | ■ | exclusion | unknown to HOPS |
neighborhood diversity | ■ | exclusion | exclusion |
NLC-width | ■ | exclusion | exclusion |
NLCT-width | ■ | exclusion | exclusion |
nowhere dense | ■ | exclusion | unknown to HOPS |
odd cycle transversal | ■ | exclusion | exclusion |
outerplanar | ■ | unknown to HOPS | exclusion |
overlap treewidth | ■ | exclusion | exclusion |
path | ■ | unbounded | exclusion |
pathwidth | ■ | exclusion | exclusion |
pathwidth+maxdegree | ■ | exclusion | exclusion |
perfect | ■ | unbounded | exclusion |
planar | ■ | unbounded | exclusion |
radius-inf flip-width | ■ | exclusion | exclusion |
radius-r flip-width | ■ | exclusion | unknown to HOPS |
rank-width | ■ | exclusion | exclusion |
series-parallel | ■ | unknown to HOPS | unknown to HOPS |
shrub-depth | ■ | exclusion | exclusion |
sim-width | ■ | exclusion | unknown to HOPS |
size | ■ | upper bound | exclusion |
slim tree-cut width | ■ | exclusion | exclusion |
sparse twin-width | ■ | exclusion | exclusion |
star | ■ | unknown to HOPS | exclusion |
stars | ■ | unbounded | exclusion |
strong coloring number | ■ | exclusion | exclusion |
strong d-coloring number | ■ | exclusion | unknown to HOPS |
strong inf-coloring number | ■ | exclusion | exclusion |
topological bandwidth | ■ | unknown to HOPS | exclusion |
tree | ■ | unbounded | exclusion |
tree-cut width | ■ | exclusion | exclusion |
tree-independence number | ■ | exclusion | unknown to HOPS |
tree-partition-width | ■ | exclusion | exclusion |
treebandwidth | ■ | exclusion | exclusion |
treedepth | ■ | exclusion | exclusion |
treelength | ■ | exclusion | upper bound |
treespan | ■ | exclusion | exclusion |
treewidth | ■ | exclusion | exclusion |
twin-cover number | ■ | exclusion | exclusion |
twin-width | ■ | exclusion | exclusion |
vertex connectivity | ■ | unknown to HOPS | unknown to HOPS |
vertex cover | ■ | exclusion | exclusion |
vertex integrity | ■ | exclusion | exclusion |
weak coloring number | ■ | exclusion | exclusion |
weak d-coloring number | ■ | exclusion | unknown to HOPS |
weak inf-coloring number | ■ | exclusion | exclusion |
weakly sparse | ■ | exclusion | unknown to HOPS |
weakly sparse and merge width | ■ | exclusion | exclusion |
Results
- 2008 Spanning Trees with Many Leaves and Average Distance by DeLaViña, Waller
- page 5 : bipartite number upper bounds average distance by a linear function – Theorem 9 (Main Theorem). Let $G$ be a graph. Then $\bar{D} < \frac b2 + \frac 12$. …
- assumed
- maximum independent set upper bounds bipartite number by a linear function – folklore: Each of the parts of the maximum induced bipartite subgraph is an independent set. Hence, the bipartite number is at most twice the size of the maximum independent set.
- bipartite number upper bounds maximum independent set by a linear function – As one can pick the maximum independent set as one side of an induced bipartite subgraph we know that the maximum one has size at least the size of the maximum independent set.
- bipartite number is equivalent to bipartite number – assumed