A finite basis characterization of alpha-split colorings (Q1850023)

A graph is called split if there exists a partition of its vertices into two sets so that one set induces a clique and the second set induces an independent set. This concept can be generalized as follows: Fix \(t>1\), a positive integer, and \({\mathbf a}=(a_1,\dots,a_t)\) a vector of nonnegative integers. A \(t\)-colouring of the edges of a complete graph is called \({\mathbf a}\)-split if there exists a partition of the vertices into \(t\) sets \(V_1,\dots,V_t\) such that every set of \(a_i+1\) vertices in \(V_i\) contains an edge of colour \(i\), for \(i=1,2,\dots,t\). It is shown that for any given \({\mathbf a}\), the family of \({\mathbf a}\)-split colourings is characterized by a finite set of forbidden induced subcolourings. The result is obtained by the combination of a theorem of \textit{M. Deza} [J. Comb. Theory, Ser. B 16, 166-167 (1974; Zbl 0263.05007)] and Ramsey's theorem. An analogous hypergraph version is obtained as well. The authors also treat some variations of the problem. The paper extends works of \textit{A. E. Kézdy} et al. [J. Comb. Theory, Ser. A 73, 353-359 (1996; Zbl 0844.05003)] and \textit{A. Gyárfás} [J. Comb. Theory, Ser. A 81, 255-261 (1998; Zbl 0893.05012)].