DIMACS TR: 2007-04
Decomposing complete edge-chromatic graphs and hypergraphs
Author: Vladimir Gurvich
ABSTRACT
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