A Domatic Analogue of $χ$-Bounded Graph Classes and the Gyárfás-Sumner Conjecture

Quentin Chuet, Selma Djelloul, Hoang La, François Pirot, Hossein Zaredehabadi

arXivarxiv/2606.02030Jun 1, 2026math.COscore 0

Given a graph $G$, a dominating set is a subset $X\subseteq V(G)$ such that $N[X]=V(G)$. The \emph{domatic number} of $G$, denoted ${\rm dom}(G)$, is the maximum size of a partition of $V(G)$ into dominating sets. In analogy with the lower bound of the chromatic number by the clique number, the domatic number satisfies the upper bound ${\rm dom}(G)\le δ(G)+1$ where $δ(G)$ is the minimum degree of $G$. Therefore, as an analogue of the notion of $χ$-bounded graph classes, we say that a class of graphs $\mathscr{G}$ is \emph{DOM-bounded} if there exists a positive unbounded function…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2606.02030
curl -X POST /api/v1/records/arxiv/2606.02030/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.02030/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'