A generalization of Vizing's Theorem?
Status Open · unsolvedmath.comLLM status Open unverified
Top Open Problems Not reported cataloguedOpenOpenStatement
Definitions and mathematical statement
Fix integers $d\ge2$ and $r\ge1$. A finite simple $d$-uniform hypergraph $H=(V,\mathcal E)$ consists of a finite vertex set and a set of distinct $d$-element subsets of $V$, called edges. For a $(d-1)$-element set $S\subseteq V$, its codegree is the number of hyperedges containing $S$. Assume every such codegree is at most $r$.The conjecture asks for an assignment \[ c:\mathcal E\longrightarrow\{1,\ldots,r+d-1\} \] such that $c(e)\ne c(f)$ whenever distinct hyperedges $e,f$ have $|e\cap f|=d-1$. This is a coloring of hyperedges with a specific conflict rule: pairs sharing fewer than $d-1$ vertices may receive the same color, even when their intersection is nonempty.
Equivalently, form the ordinary conflict graph with vertex set $\mathcal E$ and join exactly those pairs of hyperedges that overlap in $d-1$ vertices. The assertion is that this graph has chromatic number at most $r+d-1$ under the stated codegree bound. Both parameters are universal; the bound is independent of $|V|$ and $|\mathcal E|$.
When $d=2$, the hypergraph is an ordinary simple graph, codegree is vertex degree, and the conflict rule is the usual proper edge-coloring rule. This recovers the degree-plus-one edge-coloring bound. For larger $d$, replacing the conflict rule by the usual requirement that all intersecting hyperedges differ would change the problem substantially.
Short English statement
Can d-uniform hyperedges with codegree at most r be colored with r+d−1 colors when only overlaps of size d−1 create conflicts?Sources
- S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3199 (OPG-182), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
- S2 Open Problem Garden, A generalization of Vizing's Theorem?. Original problem and discussion. http://www.openproblemgarden.org/op/a_generalization_of_vizings_theorem.
Statement licence: CC-BY-4.0 · Source file
Contributions 0
No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.