Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

A dd-graph G=(V;E1,…,Ed)G=(V;E1,…,Ed) is a complete graph whose edges are colored by dd colors, that is, partitioned into dd subsets some of which might be empty. We say that a dd-graph GG is complementary connected (CC)   if the complement to each chromatic component of GG is connected on VV. We prove that every such dd-graph contains a sub-dd-graph ΠΠ or Δ, where ΠΠ has four vertices and two non-empty chromatic components each of which is a P4P4, while Δ is a three-colored triangle. This statement implies that each ΠΠ- and Δ-free dd-graph is uniquely decomposable in accordance with a tree T=T(G)T=T(G) whose leaves are the vertices of VV and the interior vertices of TT are labeled by the colors 1,…d1,…d. Such a tree is naturally interpreted as a positional game form (with perfect information and without moves of chance) of dd players I={1,…,d}I={1,…,d} and nn outcomes V={v1,…,vn}V={v1,…,vn}. Thus, we get a one-to-one correspondence between these game forms and ΠΠ- and Δ-free dd-graphs. As a corollary, we obtain a characterization of the normal forms of positional games with perfect information and, in case d=2d=2, several characterizations of the read-once Boolean functions. These results are not new; in fact, they are 30 and, in case d=2d=2, even 40 years old. Yet, some important proofs did not appear in English.Gyárfás and Simonyi recently proved a similar decomposition theorem for the Δ-free dd-graphs. They showed that each Δ-free dd-graph can be obtained from the dd-graphs with only two non-empty chromatic components by successive substitutions. This theorem is based on results by Gallai, Lovász, Cameron and Edmonds. We obtain some new applications of these results.