## Not complementary connected and not CIS d-graphs form weakly monotone families

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.