On an Erdős--Lov'asz problem: 3-critical 3-graphs of minimum degree 7
By: Ruiliang Li
Erdős and Lov'asz asked whether there exists a "3-critical" 3-uniform hypergraph in which every vertex has degree at least 7. The original formulation does not specify what 3-critical means, and two non-equivalent notions have appeared in the literature and in later discussions of the problem. In this paper we resolve the question under both interpretations. For the transversal interpretation (criticality with respect to the transversal number), we prove that a 3-uniform hypergraph $H$ with $τ(H)=3$ and $τ(H-e)=2$ for every edge $e$ has at most 10 edges; in particular, $δ(H)\le 6$, and this bound is sharp, witnessed by the complete 3-graph $K^{(3)}_5$. For the chromatic interpretation (criticality with respect to weak vertex-colourings), we give an explicit 3-uniform hypergraph on 9 vertices with $χ(H)=3$ and minimum degree $δ(H)=7$ such that deleting any single edge or any single vertex makes it 2-colourable. The criticality of the example is certified by explicit witness 2-colourings listed in the appendices, together with a short verification script.
Similar Papers
On arc-density of pushably $3$-critical oriented graphs
Discrete Mathematics
Helps color maps with fewer colors.
Independent sets and colorings of $K_{t,t,t}$-free graphs
Combinatorics
Helps computers color maps with fewer colors.
Extremal chemical graphs of maximum degree at most 3 for 33 degree-based topological indices
Combinatorics
Finds simple rules for complex chemical structures.