Odd-intersection edge coloring of Kₙ

Status partial high confidence

Bennett, Heath, and Zerbib (arXiv:2307.01314, July 2023) directly study the quantity g(G,H) — the minimum number of colors to edge-color G so that every copy of H has an odd color class — introduced as a tool for bounding graph-codes. They establish g(K_n, K_5) ≤ n^{o(1)} and g(K_{n,n}, C_4) = n/2 + o(n), providing the first non-trivial estimates for specific choices of H. The general problem for arbitrary H remains open, and subsequent 2025 papers continue developing the odd-Ramsey framework.

Cited literature (1)

• partial Edge-coloring a graph $G$ so that every copy of a graph $H$ has an odd color class (2023)
  Patrick Bennett, Emily Heath, Shira Zerbib · arXiv preprint · arXiv:2307.01314

  Defines g(G,H) as the minimum number of colors to edge-color G so every copy of H has an odd color class, and proves g(K_n, K_5) ≤ n^{o(1)} and g(K_{n,n}, C_4) = n/2 + o(n), giving the first estimates for specific graphs H.

Reviewer notes. The follow-up paper arXiv:2307.01314 formalises the open problem under the name g(G,H) and solves it for G=K_n with H=K_5 and G=K_{n,n} with H=C_4, but the general problem for arbitrary H in K_n is still open. Search results also surfaced several 2025 papers on odd Ramsey numbers (arXiv:2507.19456, arXiv:2511.10497, arXiv:2605.07322) that extend this line of work further, but those were not individually verified via WebFetch within the 5-call cap.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).