pith. sign in

arxiv: 2307.01314 · v3 · pith:2XRCUZV5new · submitted 2023-07-03 · 🧮 math.CO

Edge-coloring a graph G so that every copy of a graph H has an odd color class

classification 🧮 math.CO
keywords graphclasscodecolorcopyeveryalonbound
0
0 comments X
read the original abstract

Recently, Alon introduced the notion of an $H$-code for a graph $H$: a collection of graphs on vertex set $[n]$ is an $H$-code if it contains no two members whose symmetric difference is isomorphic to $H$. Let $D_{H}(n)$ denote the maximum possible cardinality of an $H$-code, and let $d_{H}(n)=D_{H}(n)/2^{n \choose 2}$. Alon observed that a lower bound on $d_{H}(n)$ can be obtained by attaining an upper bound on the number of colors needed to edge-color $K_n$ so that every copy of $H$ has an odd color class. Motivated by this observation, we define $g(G,H)$ to be the minimum number of colors needed to edge-color a graph $G$ so that every copy of $H$ has an odd color class. We prove $g(K_n,K_5) \le n^{o(1)}$ and $g(K_{n,n}, C_4)= n/2+o(n)$. The first result shows $d_{K_5}(n) \ge \frac{1}{n^{o(1)}}$ and was obtained independently in arXiv:2306.14682.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. New results on the odd- and unique-Ramsey numbers

    math.CO 2026-05 unverdicted novelty 6.0

    New lower bounds r_odd(n, K_{s,t}) > n^{1/(s/2 + 1/(2 floor(t/8)))} for odd s even t, r_u(n, C_n) > n/4 creating a polynomial gap, and odd-Ramsey number of Hamilton cycles >1 in super-Dirac graphs.