maximum independent set

functionally equivalent to: bipartite number

providers: ISGCI

Definition: Is the cardinality of a maximum vertex set such that no pair of vertices in the set are connected by an edge.

Relations

Other		Relation from	Relation to
acyclic chromatic number	blue■	exclusion	exclusion
admissibility	blue■	exclusion	exclusion
arboricity	blue■	exclusion	exclusion
average degree	blue■	exclusion	exclusion
average distance	red■	exclusion	upper bound
bandwidth	cyan■	unknown to HOPS	exclusion
bipartite	blue■	unbounded	exclusion
bipartite number	yellow■	upper bound	upper bound
bisection bandwidth	cyan■	unknown to HOPS	exclusion
block	blue■	unbounded	exclusion
book thickness	blue■	exclusion	exclusion
boolean width	blue■	exclusion	exclusion
bounded components	blue■	exclusion	exclusion
bounded expansion	blue■	exclusion	avoids
boxicity	blue■	exclusion	exclusion
branch width	blue■	exclusion	exclusion
c-closure	blue■	exclusion	exclusion
carving-width	blue■	exclusion	exclusion
chi-bounded	magenta■	exclusion	unknown to HOPS
chordal	blue■	unbounded	exclusion
chordality	blue■	exclusion	exclusion
chromatic number	blue■	exclusion	exclusion
clique cover number	green■	upper bound	exclusion
clique-tree-width	blue■	exclusion	exclusion
clique-width	blue■	exclusion	exclusion
cluster	blue■	unbounded	exclusion
co-cluster	blue■	unbounded	exclusion
cograph	blue■	unbounded	exclusion
complete	green■	upper bound	exclusion
connected	blue■	exclusion	avoids
contraction complexity	blue■	exclusion	exclusion
cutwidth	blue■	exclusion	exclusion
cycle	cyan■	unknown to HOPS	exclusion
cycles	cyan■	unknown to HOPS	exclusion
d-admissibility	magenta■	exclusion	unknown to HOPS
d-path-free	blue■	exclusion	exclusion
degeneracy	blue■	exclusion	exclusion
degree treewidth	blue■	exclusion	exclusion
diameter	red■	exclusion	upper bound
diameter+max degree	blue■	exclusion	exclusion
distance to bipartite	blue■	exclusion	exclusion
distance to block	blue■	exclusion	exclusion
distance to bounded components	blue■	exclusion	exclusion
distance to chordal	blue■	exclusion	exclusion
distance to cluster	blue■	exclusion	exclusion
distance to co-cluster	blue■	exclusion	exclusion
distance to cograph	blue■	exclusion	exclusion
distance to complete	green■	upper bound	exclusion
distance to edgeless	blue■	exclusion	exclusion
distance to forest	blue■	exclusion	exclusion
distance to interval	blue■	exclusion	exclusion
distance to linear forest	blue■	exclusion	exclusion
distance to maximum degree	blue■	exclusion	exclusion
distance to outerplanar	blue■	exclusion	exclusion
distance to perfect	blue■	exclusion	exclusion
distance to planar	blue■	exclusion	exclusion
distance to stars	blue■	exclusion	exclusion
domatic number	blue■	exclusion	exclusion
domination number	red■	exclusion	upper bound
domino treewidth	blue■	exclusion	exclusion
edge clique cover number	blue■	exclusion	exclusion
edge connectivity	blue■	exclusion	exclusion
edge-cut width	blue■	exclusion	exclusion
edge-treewidth	blue■	exclusion	exclusion
edgeless	blue■	exclusion	avoids
excluded minor	blue■	exclusion	avoids
excluded planar minor	cyan■	unknown to HOPS	avoids
excluded top-minor	blue■	exclusion	avoids
feedback edge set	blue■	exclusion	exclusion
feedback vertex set	blue■	exclusion	exclusion
flip-width	magenta■	exclusion	unknown to HOPS
forest	blue■	unbounded	exclusion
genus	blue■	exclusion	exclusion
grid	blue■	unbounded	exclusion
h-index	blue■	exclusion	exclusion
interval	blue■	unbounded	exclusion
iterated type partitions	blue■	exclusion	exclusion
linear clique-width	blue■	exclusion	exclusion
linear forest	blue■	unbounded	exclusion
linear NLC-width	blue■	exclusion	exclusion
linear rank-width	blue■	exclusion	exclusion
maximum clique	blue■	exclusion	exclusion
maximum degree	blue■	exclusion	exclusion
maximum independent set	yellow■	equal	equal
maximum induced matching	red■	exclusion	upper bound
maximum leaf number	cyan■	unknown to HOPS	exclusion
maximum matching	blue■	exclusion	exclusion
maximum matching on bipartite graphs	blue■	exclusion	exclusion
merge-width	magenta■	exclusion	unknown to HOPS
mim-width	magenta■	exclusion	unknown to HOPS
minimum degree	blue■	exclusion	exclusion
mm-width	blue■	exclusion	exclusion
modular-width	blue■	exclusion	exclusion
module-width	blue■	exclusion	exclusion
monadically dependent	magenta■	exclusion	unknown to HOPS
monadically stable	magenta■	exclusion	unknown to HOPS
neighborhood diversity	blue■	exclusion	exclusion
NLC-width	blue■	exclusion	exclusion
NLCT-width	blue■	exclusion	exclusion
nowhere dense	magenta■	exclusion	unknown to HOPS
odd cycle transversal	blue■	exclusion	exclusion
outerplanar	cyan■	unknown to HOPS	exclusion
overlap treewidth	blue■	exclusion	exclusion
path	blue■	unbounded	exclusion
pathwidth	blue■	exclusion	exclusion
pathwidth+maxdegree	blue■	exclusion	exclusion
perfect	blue■	unbounded	exclusion
planar	blue■	unbounded	exclusion
radius-inf flip-width	blue■	exclusion	exclusion
radius-r flip-width	magenta■	exclusion	unknown to HOPS
rank-width	blue■	exclusion	exclusion
series-parallel	gray■	unknown to HOPS	unknown to HOPS
shrub-depth	blue■	exclusion	exclusion
sim-width	magenta■	exclusion	unknown to HOPS
size	green■	upper bound	exclusion
slim tree-cut width	blue■	exclusion	exclusion
sparse twin-width	blue■	exclusion	exclusion
star	cyan■	unknown to HOPS	exclusion
stars	blue■	unbounded	exclusion
strong coloring number	blue■	exclusion	exclusion
strong d-coloring number	magenta■	exclusion	unknown to HOPS
strong inf-coloring number	blue■	exclusion	exclusion
topological bandwidth	cyan■	unknown to HOPS	exclusion
tree	blue■	unbounded	exclusion
tree-cut width	blue■	exclusion	exclusion
tree-independence number	magenta■	exclusion	unknown to HOPS
tree-partition-width	blue■	exclusion	exclusion
treebandwidth	blue■	exclusion	exclusion
treedepth	blue■	exclusion	exclusion
treelength	red■	exclusion	upper bound
treespan	blue■	exclusion	exclusion
treewidth	blue■	exclusion	exclusion
twin-cover number	blue■	exclusion	exclusion
twin-width	blue■	exclusion	exclusion
vertex connectivity	gray■	unknown to HOPS	unknown to HOPS
vertex cover	blue■	exclusion	exclusion
vertex integrity	blue■	exclusion	exclusion
weak coloring number	blue■	exclusion	exclusion
weak d-coloring number	magenta■	exclusion	unknown to HOPS
weak inf-coloring number	blue■	exclusion	exclusion
weakly sparse	magenta■	exclusion	unknown to HOPS
weakly sparse and merge width	blue■	exclusion	exclusion

Results

2019 The Graph Parameter Hierarchy by Sorge
- page 11 : clique cover number upper bounds maximum independent set by a linear function – Lemma 4.26. The minimum clique cover number $c$ strictly upper bounds the independence number $\alpha$.
1988 The average distanceisnot morethan the independence number by Chung
- maximum independent set upper bounds average distance by a linear function – [ed. paraphrased from another source] Let $G$ be a graph. Then $\bar{D} \le \alpha$, with equality holding if and only if $G$ is complete.
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.
- maximum independent set is equivalent to maximum independent set – assumed
unknown source
- maximum independent set upper bounds domination number by a linear function – Every maximal independent set is also a dominating set because any undominated vertex could be added to the independent set.
- maximum independent set upper bounds maximum induced matching by a linear function – Each edge of the induced matching can host at one vertex of the independent set.
- graph classes with bounded maximum independent set are not bounded clique cover number
- graph classes with bounded domination number are not bounded maximum independent set