bipartite number

Relations

Other	Relation from	Relation to
acyclic chromatic number	unknown to HOPS	exclusion
arboricity	unknown to HOPS	exclusion
average degree	unknown to HOPS	exclusion
average distance	upper bound	unknown to HOPS
bandwidth	unknown to HOPS	exclusion
bipartite	unknown to HOPS	exclusion
bisection bandwidth	unknown to HOPS	exclusion
block	unknown to HOPS	exclusion
book thickness	unknown to HOPS	exclusion
boolean width	unknown to HOPS	exclusion
bounded components	upper bound	exclusion
boxicity	unknown to HOPS	exclusion
branch width	unknown to HOPS	exclusion
c-closure	unknown to HOPS	exclusion
carving-width	unknown to HOPS	exclusion
chordal	unknown to HOPS	exclusion
chordality	unknown to HOPS	exclusion
chromatic number	unknown to HOPS	exclusion
clique cover number	upper bound	exclusion
clique-tree-width	unknown to HOPS	exclusion
clique-width	unknown to HOPS	exclusion
cluster	constant	exclusion
co-cluster	constant	exclusion
cograph	constant	exclusion
complete	constant	exclusion
connected	unknown to HOPS	unknown to HOPS
cutwidth	unknown to HOPS	exclusion
cycle	unknown to HOPS	exclusion
cycles	unknown to HOPS	exclusion
d-path-free	upper bound	exclusion
degeneracy	unknown to HOPS	exclusion
degree treewidth	unknown to HOPS	exclusion
diameter	upper bound	unknown to HOPS
diameter+max degree	upper bound	exclusion
disjoint cycles	unknown to HOPS	exclusion
distance to bipartite	unknown to HOPS	exclusion
distance to block	unknown to HOPS	exclusion
distance to bounded components	upper bound	exclusion
distance to chordal	unknown to HOPS	exclusion
distance to cluster	unknown to HOPS	exclusion
distance to co-cluster	upper bound	exclusion
distance to cograph	upper bound	exclusion
distance to complete	upper bound	exclusion
distance to edgeless	upper bound	exclusion
distance to forest	unknown to HOPS	exclusion
distance to interval	unknown to HOPS	exclusion
distance to linear forest	unknown to HOPS	exclusion
distance to maximum degree	unknown to HOPS	exclusion
distance to outerplanar	unknown to HOPS	exclusion
distance to perfect	unknown to HOPS	exclusion
distance to planar	unknown to HOPS	exclusion
distance to stars	upper bound	exclusion
domatic number	unknown to HOPS	exclusion
domination number	upper bound	exclusion
edge clique cover number	upper bound	exclusion
edge connectivity	unknown to HOPS	exclusion
edgeless	constant	exclusion
feedback edge set	unknown to HOPS	exclusion
feedback vertex set	unknown to HOPS	exclusion
forest	unknown to HOPS	exclusion
genus	unknown to HOPS	exclusion
girth	unknown to HOPS	unknown to HOPS
grid	unknown to HOPS	exclusion
h-index	unknown to HOPS	exclusion
inf-flip-width	unknown to HOPS	exclusion
interval	unknown to HOPS	exclusion
iterated type partitions	upper bound	exclusion
linear clique-width	unknown to HOPS	exclusion
linear forest	unknown to HOPS	exclusion
linear NLC-width	unknown to HOPS	exclusion
linear rank-width	unknown to HOPS	exclusion
maximum clique	unknown to HOPS	exclusion
maximum degree	unknown to HOPS	exclusion
maximum independent set	upper bound	exclusion
maximum induced matching	upper bound	unknown to HOPS
maximum leaf number	unknown to HOPS	exclusion
maximum matching	upper bound	exclusion
maximum matching on bipartite graphs	upper bound	exclusion
mim-width	unknown to HOPS	unknown to HOPS
minimum degree	unknown to HOPS	exclusion
mm-width	unknown to HOPS	exclusion
modular-width	upper bound	exclusion
module-width	unknown to HOPS	exclusion
neighborhood diversity	upper bound	exclusion
NLC-width	unknown to HOPS	exclusion
NLCT-width	unknown to HOPS	exclusion
odd cycle transversal	unknown to HOPS	exclusion
outerplanar	unknown to HOPS	exclusion
path	unknown to HOPS	exclusion
pathwidth	unknown to HOPS	exclusion
pathwidth+maxdegree	unknown to HOPS	exclusion
perfect	unknown to HOPS	exclusion
planar	unknown to HOPS	exclusion
radius-r flip-width	unknown to HOPS	unknown to HOPS
rank-width	unknown to HOPS	exclusion
shrub-depth	unknown to HOPS	exclusion
sim-width	unknown to HOPS	unknown to HOPS
star	constant	exclusion
stars	constant	exclusion
topological bandwidth	unknown to HOPS	exclusion
tree	unknown to HOPS	exclusion
tree-independence number	unknown to HOPS	unknown to HOPS
treedepth	upper bound	exclusion
treelength	unknown to HOPS	unknown to HOPS
treewidth	unknown to HOPS	exclusion
twin-cover number	upper bound	exclusion
twin-width	unknown to HOPS	exclusion
vertex connectivity	unknown to HOPS	exclusion
vertex cover	upper bound	exclusion
vertex integrity	upper bound	exclusion

Results

2008 Spanning Trees with Many Leaves and Average Distance by DeLaViña, Waller
- page 5 : average distance upper bounds bipartite number by a linear function – Theorem 9 (Main Theorem). Let $G$ be a graph. Then $\bar{D} < \frac b2 + \frac 12$. …
assumed
- bipartite number – Bipartite number of $G$ is the maximum order of an induced bipartite subgraph.
- maximum independent set upper bounds bipartite number by a linear function – folklore