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

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 c h o o s e 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}) l e n^{o (1)}

and

g (K_{n, n}, C_{4}) l e f r a c t 2 (t - 1) n + o (n)

for all odd integers

t g e q 5

. The first result shows

d_{K_{5}} (n) g e f r a c 1 n^{o (1)}

and was obtained independently in arXiv:2306.14682.

This page was built for publication: Edge-coloring a graph $G$ so that every copy of a graph $H$ has an odd color class