A finite basis characterization of α-split colorings Original Research Article

Fix t>1, a positive integer, and a=(a1,…,at) a vector of nonnegative integers. A t-coloring of the edges of a complete graph is called a-split if there exists a partition of the vertices into t sets V1,…,Vt such that every set of ai+1 vertices in Vi contains an edge of color i, for i=1,…,t. We combine a theorem of Deza with Ramseyʹs theorem to prove that, for any fixed a, the family of a-split colorings is characterized by a finite list of forbidden induced subcolorings. A similar hypergraph version follows from our proofs. These results generalize previous work by Kézdy et al. (J. Combin. Theory Ser. A 73(2) (1996) 353) and Gyárfás (J. Combin. Theory Ser. A 81(2) (1998) 255). We also consider other notions of splitting.