DIMACS TR: 2007-04

Decomposing complete edge-chromatic graphs and hypergraphs

Author: Vladimir Gurvich


A $d$-graph $\cG = (V; E_1, \ldots, E_d)$ is a complete graph whose edges are colored by $d$ colors, or in other words, are partitioned into $d$ subsets (some of which might be empty). We say that $\cG$ is {\em complementary connected} if the complement to each chromatic component of $\cG$ is connected on $V$, or in other words, if for each two vertices $u,w \in V$ and color $i \in I = \{1, \ldots, d\}$ there is a path between $u$ and $w$ without edges of $E_i$. We show that every such $d$-graph contains a subgraph $\Pi$ or $\Delta$ , where $\Pi$ has 4 vertices and 2 non-empty chromatic components each of which is a $P_4$, while $\Delta$ is the three-colored triangle. This simple statement implies that each $\Pi$- and $\Delta$-free $d$-graph is uniquely decomposable in accordance with a tree $T = T(\cG)$ whose leaves are the vertices of $V$ and other vertices of $T$ are labeled by the colors of $I$. We can naturally interpret such a tree as a positional game (with perfect information and without moves of chance) of $d$ players $I = \{1, \ldots, d\}$ and $n$ outcomes $V = \{v_1, \ldots, v_n\}$. Thus, we get a one-to-one correspondence between these games and $\Pi$- and $\Delta$-free $d$-graphs and, as a corollary, a characterization of the normal forms of positional games with perfect information. Another corollary of the above decomposition of $d$-graphs in case $d=2$ is a characterization of the read-once Boolean functions. These results are not new; in fact, they are 25-35 years old. Yet, some important proofs did not appear in English. Gy\'arf\'as and Simonyi recently proved a similar decomposition theorem for $\Delta$-free $d$-graph. They showed that each such $d$-graph can be obtained from $2$-graphs by substitutions. This theorem is based on results by Gallai, Cameron and Edmonds. We get some new applications of these results.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2007/2007-04.pdf
DIMACS Home Page