DIMACS TR: 2009-08
Not complementary connected and not CIS d-graphs form weakly monotone families
Authors: Diogo V. Andrade, Endre Boros and Vladimir Gurvich
ABSTRACT
A d-graph G = (V;E1,...,Ed) is a complete graph whose edges are arbitrarily partitioned into d subsets (colored with d colors); G is a Gallai d-graph if it contains no three-colored triangle $\Delta$; furthermore, G is a CIS d-graph if $\cup_{i=1}^d Si\not= \emptyset$ for every set-family S = {Si | i in [d] }, where Si in V is a maximal independent set of Gi = (V;Ei), the ith chromatic component of G, for all i in [d] = {1 ... d}. A conjecture suggested in 1978 by the third author says that every CIS d-graph is a Gallai d-graph. In this paper we obtain a partial result. Let $\pi$ be the two-colored d-graph on four vertices whose two non-empty chromatic components are isomorphic to P4. It is easily seen that $\pi$ and $\Delta$ are not CIS d-graphs but become CIS after eliminating any vertex. We prove that no other d-graph has this property, that is, every non-CIS d-graph G distinct from $\pi$ and $\Delta$ contains a vertex v in V such that the sub-d-graph G[V \ {v}] is still non-CIS. This result easily follows if the above $\Delta$-conjecture is true, yet, we prove it independently.
A d-graph G = (V;E1,...,Ed) is complementary connected (CC) if the complement
Gi = (V;Ei) = (V, U Ej, j in [d]\ {i}) to its ith chromatic component is connected for
every i in [d]. It is known that every CC d-graph G, distinct from \pi and \Delta, and a single
vertex, contains a vertex v 2 V such that the reduced sub-d-graph G[V \ {v}] is still
CC. It is not difficult to show that every non-CC d-graph with contains a vertex v in V
such that the sub-d-graph G[V \ {v}] is not CC.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2009/2009-08.pdf
DIMACS Home Page