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 ‐code for a graph : a collection of graphs on vertex set is an ‐code if it contains no two members whose symmetric difference is isomorphic to . Let denote the maximum possible cardinality of an ‐code, and let . Alon observed that a lower bound on can be obtained by attaining an upper bound on the number of colors needed to edge‐color so that every copy of has an odd color class. Motivated by this observation, we define to be the minimum number of colors needed to edge‐color a graph so that every copy of has an odd color class. We prove and . The first result shows and was obtained independently in [9].