Injective coloring conjecture for regular uniform hypergraphs

About 6 years old · traced to

Let r≥2r\geq 2. An injective qq-coloring of an rr-uniform hypergraph is a coloring of its vertices with qq colors such that any two edges sharing r−1r-1 vertices have distinct color sets. Injective coloring conjecture. There exist constants c,c′>0c,c'>0 such that, whenever HH is a Δ\Delta-regular rr-graph with maximum (r−1)(r-1)-degree at most DD, HH has a spanning subgraph GG of minimum degree at least cΔc\Delta with an injective c′Dc'D-coloring. The source notes that an injectively colored subgraph with linearly many edges is already available; the open difficulty is preserving minimum degree, so the conjecture remains open.

References

Primary source

Sam Spiro and Jacques Verstraëte, “Relative Turán Problems for Uniform Hypergraphs”, arXiv:2009.02416 (2021).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.