Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

AbstractA d-graph G=(V;E1,…,Ed) is a complete graph whose edges are colored by d colors, that is, partitioned into d subsets some of which might be empty. We say that a d-graph G is complementary connected (CC) if the complement to each chromatic component of G is connected on V. We prove that every such d-graph contains a sub-d-graph Π or Δ, where Π has four vertices and two non-empty chromatic components each of which is a P4, while Δ is a three-colored triangle. This statement implies that each Π- and Δ-free d-graph is uniquely decomposable in accordance with a tree T=T(G) whose leaves are the vertices of V and the interior vertices of T are labeled by the colors 1,…d. Such a tree is naturally interpreted as a positional game form (with perfect information and without moves of chance) of d players I={1,…,d} and n outcomes V={v1,…,vn}. Thus, we get a one-to-one correspondence between these game forms and Π- and Δ-free d-graphs. As a corollary, we obtain a characterization of the normal forms of positional games with perfect information and, in case d=2, several characterizations of the read-once Boolean functions. These results are not new; in fact, they are 30 and, in case d=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 d-graphs. They showed that each Δ-free d-graph can be obtained from the d-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