TY - JOUR
T1 - Not complementary connected and not CIS d-graphs form weakly monotone families
AU - Andrade, Diogo V.
AU - Boros, Endre
AU - Gurvich, Vladimir
N1 - Funding Information: This research was partially supported by DIMACS, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, and by Graduate School of Information Science and Technology, University of Tokyo; the third author gratefully acknowledges also the partial support of the Aarhus University Research Foundation and Center of Algorithmic Game Theory.
PY - 2010/3/6
Y1 - 2010/3/6
N2 - 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 3-colored triangle Δ; furthermore, G is a CIS d-graph if {n-ary intersection}i = 1d Si ≠ 0{combining long solidus overlay} for every set-family S = {Si | i ∈ [d]}, where Si ⊆ V is a maximal independent set of Gi = (V, Ei), the ith chromatic component of G, for all i ∈ [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 article, we obtain a partial result. Let Π be the 2-colored d-graph on four vertices whose two non-empty chromatic components are isomorphic to P4. It is easily seen that Π and Δ 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 Π and Δ contains a vertex v ∈ V such that the sub-d-graph G [V {set minus} {v}] is still non-CIS. This result easily follows if the above Δ-conjecture is true, yet, we prove it independently. A d-graph G = (V ; E1, ..., Ed) is complementary connected (CC) if the complement over(G, -)i = (V, over(E, -)i) = (V, {n-ary union}j ∈ [d] {set minus} {i} Ej) to its ith chromatic component is connected for every i ∈ [d]. It is known that every CC d-graph G, distinct from Π, Δ, and a single vertex, contains a vertex v ∈ V such that the reduced sub-d-graph G [V {set minus} {v}] is still CC. It is not difficult to show that every non-CC d-graph with at least two vertices contains a vertex v ∈ V such that the sub-d-graph G [V {set minus} {v}] is not CC.
AB - 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 3-colored triangle Δ; furthermore, G is a CIS d-graph if {n-ary intersection}i = 1d Si ≠ 0{combining long solidus overlay} for every set-family S = {Si | i ∈ [d]}, where Si ⊆ V is a maximal independent set of Gi = (V, Ei), the ith chromatic component of G, for all i ∈ [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 article, we obtain a partial result. Let Π be the 2-colored d-graph on four vertices whose two non-empty chromatic components are isomorphic to P4. It is easily seen that Π and Δ 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 Π and Δ contains a vertex v ∈ V such that the sub-d-graph G [V {set minus} {v}] is still non-CIS. This result easily follows if the above Δ-conjecture is true, yet, we prove it independently. A d-graph G = (V ; E1, ..., Ed) is complementary connected (CC) if the complement over(G, -)i = (V, over(E, -)i) = (V, {n-ary union}j ∈ [d] {set minus} {i} Ej) to its ith chromatic component is connected for every i ∈ [d]. It is known that every CC d-graph G, distinct from Π, Δ, and a single vertex, contains a vertex v ∈ V such that the reduced sub-d-graph G [V {set minus} {v}] is still CC. It is not difficult to show that every non-CC d-graph with at least two vertices contains a vertex v ∈ V such that the sub-d-graph G [V {set minus} {v}] is not CC.
KW - Complementary connected
KW - Gallai
KW - Minimal and locally minimal
KW - Weakly monotone
KW - d-graph
UR - http://www.scopus.com/inward/record.url?scp=72549118428&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=72549118428&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2009.11.006
DO - 10.1016/j.disc.2009.11.006
M3 - Article
SN - 0012-365X
VL - 310
SP - 1089
EP - 1096
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 5
ER -