Asymptotic conjecture for the domatic number of almost regular graphs

From papers

Let kk be a positive integer and let C1C\geq 1 be a real number. A graph GG is (k,C)(k,C)-regular if its minimum degree is δ(G)=k\delta(G)=k and its maximum degree satisfies Δ(G)kC\Delta(G)\leq kC. Let f(k,C)f(k,C) be the minimum possible domatic number dom(G)dom(G) over all (k,C)(k,C)-regular graphs.

Asymptotic domatic-number conjecture. For every fixed real number C1C\geq 1,

f(k,C)=klnk(1+ok(1)).f(k,C)=\frac{k}{\ln k}(1+o_k(1)).

The preceding bounds show that f(k,C)f(k,C) has order of magnitude k/lnkk/\ln k for fixed C>1C>1, while the conjecture identifies the sharp leading constant and extends the proposed asymptotic to C=1C=1, the regular-graph case. The source does not state a resolution, so the conjecture is recorded as open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Raphael Yuster, “The domatic number of regular and almost regular graphs”, arXiv:math/0111257 (2001).

Solutions 0

No solutions have been posted yet.