Edge-coloring a graph $G$ so that every copy of a graph $H$ has an odd color class
Preprint
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.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Ramsey theory constructions from hypergraph matchingsProceedings of the American Mathematical Society, 2024
- K4-intersecting families of graphsJournal of Combinatorial Theory, Series B, 2023
- Structured Codes of GraphsSIAM Journal on Discrete Mathematics, 2023
- Triangle-intersecting families of graphsJournal of the European Mathematical Society, 2012
- Note – Edge-Coloring Cliques with Three Colors on All 4-CliquesCombinatorica, 1998
- A variant of the classical Ramsey problemCombinatorica, 1997