bipartite
tags: coloring
equivalent to: bipartite
providers: ISGCI
Relations
Other | Relation from | Relation to |
---|---|---|
acyclic chromatic number | exclusion | unbounded |
arboricity | exclusion | unbounded |
average degree | exclusion | unbounded |
average distance | exclusion | unbounded |
bandwidth | exclusion | unbounded |
bipartite number | exclusion | unknown to HOPS |
bisection bandwidth | exclusion | unbounded |
block | exclusion | exclusion |
book thickness | exclusion | unbounded |
boolean width | exclusion | unbounded |
bounded components | exclusion | unbounded |
boxicity | exclusion | unknown to HOPS |
branch width | exclusion | unbounded |
c-closure | exclusion | unknown to HOPS |
carving-width | exclusion | unbounded |
chordal | exclusion | exclusion |
chordality | exclusion | constant |
chromatic number | exclusion | constant |
clique cover number | exclusion | unbounded |
clique-tree-width | exclusion | unbounded |
clique-width | exclusion | unbounded |
cluster | exclusion | exclusion |
co-cluster | exclusion | exclusion |
cograph | exclusion | exclusion |
complete | exclusion | exclusion |
connected | exclusion | unknown to HOPS |
cutwidth | exclusion | unbounded |
cycle | unknown to HOPS | exclusion |
cycles | exclusion | exclusion |
d-path-free | exclusion | unbounded |
degeneracy | exclusion | unbounded |
degree treewidth | exclusion | unbounded |
diameter | exclusion | unbounded |
diameter+max degree | exclusion | unbounded |
disjoint cycles | exclusion | exclusion |
distance to bipartite | unknown to HOPS | constant |
distance to block | exclusion | unbounded |
distance to bounded components | exclusion | unbounded |
distance to chordal | exclusion | unbounded |
distance to cluster | exclusion | unbounded |
distance to co-cluster | exclusion | unbounded |
distance to cograph | exclusion | unbounded |
distance to complete | exclusion | unbounded |
distance to edgeless | unknown to HOPS | unbounded |
distance to forest | unknown to HOPS | unbounded |
distance to interval | exclusion | unbounded |
distance to linear forest | unknown to HOPS | unbounded |
distance to maximum degree | exclusion | unbounded |
distance to outerplanar | exclusion | unbounded |
distance to perfect | exclusion | constant |
distance to planar | exclusion | unknown to HOPS |
distance to stars | unknown to HOPS | unbounded |
domatic number | exclusion | unknown to HOPS |
domination number | exclusion | unbounded |
edge clique cover number | exclusion | unbounded |
edge connectivity | exclusion | unbounded |
edgeless | inclusion | exclusion |
feedback edge set | unknown to HOPS | unbounded |
feedback vertex set | unknown to HOPS | unbounded |
forest | inclusion | exclusion |
genus | exclusion | unbounded |
girth | exclusion | unbounded |
grid | inclusion | exclusion |
h-index | exclusion | unbounded |
inf-flip-width | exclusion | unbounded |
interval | exclusion | exclusion |
iterated type partitions | exclusion | unbounded |
linear clique-width | exclusion | unbounded |
linear forest | inclusion | exclusion |
linear NLC-width | exclusion | unbounded |
linear rank-width | exclusion | unbounded |
maximum clique | exclusion | constant |
maximum degree | exclusion | unbounded |
maximum independent set | exclusion | unbounded |
maximum induced matching | exclusion | unbounded |
maximum leaf number | unknown to HOPS | unbounded |
maximum matching | unknown to HOPS | unbounded |
maximum matching on bipartite graphs | inclusion | unbounded |
mim-width | exclusion | unknown to HOPS |
minimum degree | exclusion | unbounded |
mm-width | exclusion | unbounded |
modular-width | exclusion | unbounded |
module-width | exclusion | unbounded |
neighborhood diversity | exclusion | unbounded |
NLC-width | exclusion | unbounded |
NLCT-width | exclusion | unbounded |
odd cycle transversal | unknown to HOPS | constant |
outerplanar | exclusion | exclusion |
path | inclusion | exclusion |
pathwidth | exclusion | unbounded |
pathwidth+maxdegree | exclusion | unbounded |
perfect | exclusion | inclusion |
planar | exclusion | exclusion |
radius-r flip-width | exclusion | unknown to HOPS |
rank-width | exclusion | unbounded |
shrub-depth | exclusion | unbounded |
sim-width | exclusion | unknown to HOPS |
star | inclusion | exclusion |
stars | inclusion | exclusion |
topological bandwidth | exclusion | unbounded |
tree | inclusion | exclusion |
tree-independence number | exclusion | unknown to HOPS |
treedepth | exclusion | unbounded |
treelength | exclusion | unknown to HOPS |
treewidth | exclusion | unbounded |
twin-cover number | exclusion | unbounded |
twin-width | exclusion | unknown to HOPS |
vertex connectivity | unknown to HOPS | unknown to HOPS |
vertex cover | unknown to HOPS | unbounded |
vertex integrity | exclusion | unbounded |
Results
- 2017 Graph Theory by Diestel
- page 17 : bipartite – Instead of `2-partite’ one usually says bipartite.
- 1993 The Pathwidth and Treewidth of Cographs by Bodlaender, Möhring
- unknown source
- graph class bipartite has unbounded girth
- graph class bipartite has unbounded edge connectivity
- assumed
- bipartite – A graph is bipartite if it can be partitioned into two independent sets.
- graph class bipartite is included in graph class perfect
- graph class perfect is not included in graph class bipartite
- graph class forest is included in graph class bipartite
- graph class bipartite is not included in graph class forest
- graph class grid is included in graph class bipartite
- graph class bipartite is not included in graph class grid
- graph class bipartite has constant distance to bipartite – by definition
- graphs with bounded maximum matching on bipartite graphs are included in graph class bipartite – by definition