The domatic number of regular and almost regular graphs
| dc.creator | Yuster, Raphael | |
| dc.date | 2001-11-24 | |
| dc.date.accessioned | 2026-07-07T04:44:45Z | |
| dc.date.available | 2026-07-07T04:44:45Z | |
| dc.description | The domatic number of a graph $G$, denoted $dom(G)$, is the maximum possible cardinality of a family of disjoint sets of vertices of $G$, each set being a dominating set of $G$. It is well known that every graph without isolated vertices has $dom(G) \geq 2$. For every $k$, it is known that there are graphs with minimum degree at least $k$ and with $dom(G)=2$. In this paper we prove that this is not the case if $G$ is $k$-regular or {\em almost} $k$-regular (by ``almost'' we mean that the minimum degree is $k$ and the maximum degree is at most $Ck$ for some fixed real number $C \geq 1$). In this case we prove that $dom(G) \geq (1+o_k(1))k/(2\ln k)$. We also prove that the order of magnitude $k/\ln k$ cannot be improved. One cannot replace the constant 2 with a constant smaller than 1. The proof uses the so called {\em semi-random method} which means that combinatorial objects are generated via repeated applications of the probabilistic method; in our case iterative applications of the Lovász Local Lemma. | |
| dc.description | 10 pages | |
| dc.identifier | https://arxiv.org/abs/math/0111257 | |
| dc.identifier | http://arxiv.org/abs/math/0111257 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/62721 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C69 | |
| dc.title | The domatic number of regular and almost regular graphs | |
| dc.type | text |