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

A dd-graph G=(V;E1,…,Ed)G=(V;E1,…,Ed) is a complete graph whose edges are arbitrarily partitioned into dd subsets (colored with dd colors); GG is a Gallai dd-graph if it contains no 3-colored triangle ΔΔ; furthermore, GG is a CIS dd-graph if ⋂i=1dSi≠0̸ for every set-family S={Si|i∈[d]}, where Si⊆VSi⊆V is a maximal independent set of Gi=(V,Ei)Gi=(V,Ei), the iith chromatic component of GG, for all i∈[d]={1,…,d}i∈[d]={1,…,d}. A conjecture suggested in 1978 by the third author says that every CIS dd-graph is a Gallai dd-graph. In this article, we obtain a partial result. Let ΠΠ be the 2-colored dd-graph on four vertices whose two non-empty chromatic components are isomorphic to P4P4. It is easily seen that ΠΠ and ΔΔ are not CIS dd-graphs but become CIS after eliminating any vertex. We prove that no other dd-graph has this property, that is, every non-CIS dd-graph GG distinct from ΠΠ and ΔΔ contains a vertex v∈Vv∈V such that the sub-dd-graph G[V∖{v}]G[V∖{v}] is still non-CIS. This result easily follows if the above ΔΔ-conjecture is true, yet, we prove it independently.A dd-graph G=(V;E1,…,Ed)G=(V;E1,…,Ed) is complementary connected (CC) if the complement G¯i=(V,E¯i)=(V,⋃j∈[d]∖{i}Ej) to its iith chromatic component is connected for every i∈[d]i∈[d]. It is known that every CC dd-graph GG, distinct from ΠΠ, ΔΔ, and a single vertex, contains a vertex v∈Vv∈V such that the reduced sub-dd-graph G[V∖{v}]G[V∖{v}] is still CC.It is not difficult to show that every non-CC dd-graph with at least two vertices contains a vertex v∈Vv∈V such that the sub-dd-graph G[V∖{v}]G[V∖{v}] is not CC.