Math-1359 · mathematics · Graph theory

Math-1359

A generalization of Vizing's Theorem?

Status Open · unsolvedmath.comLLM status Open unverified

Top Open Problems Not reported cataloguedOpenOpen

Statement

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

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.