domatic number

Relations

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

Results

2022 Expanding the Graph Parameter Hierarchy by Tran
- page 19 : bounded twin-cover number does not imply bounded domatic number – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
- page 19 : bounded domatic number does not imply bounded twin-cover number – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
- page 34 : bounded c-closure does not imply bounded domatic number – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
- page 34 : bounded domatic number does not imply bounded c-closure – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
Comparing Graph Parameters by Schröder
- page 16 : bounded distance to complete does not imply bounded domatic number – Proposition 3.7
- page 20 : bounded distance to co-cluster does not imply bounded domatic number – Proposition 3.12
- page 20 : bounded distance to bipartite does not imply bounded domatic number – Proposition 3.12
- page 30 : bounded bisection bandwidth does not imply bounded domatic number – Proposition 3.28
- page 31 : bounded domatic number does not imply bounded vertex connectivity – Proposition 3.30
unknown source
- minimum degree upper bounds domatic number by a linear function – The vertex of minimum degree needs to be dominated in each of the sets. As the sets cannot overlap there can be at most $k+1$ of them.
- graph class complete has unbounded domatic number – Parameter is unbounded for the graph class of cliques.
https://mathworld.wolfram.com/DomaticNumber.html
- domatic number – The maximum number of disjoint dominating sets in a domatic partition of a graph $G$ is called its domatic number $d(G)$.