Abstract
A
d
-graph
G
=
(
V
;
E
1
,
…
,
E
d
)
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
⋂
i
=
1
d
S
i
≠
0̸
for every set-family
S
=
{
S
i
|
i
∈
[
d
]
}
, where
S
i
⊆
V
is a maximal independent set of
G
i
=
(
V
,
E
i
)
, the
i
th 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
P
4
. 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
∖
{
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
;
E
1
,
…
,
E
d
)
is complementary connected (CC) if the complement
G
¯
i
=
(
V
,
E
¯
i
)
=
(
V
,
⋃
j
∈
[
d
]
∖
{
i
}
E
j
)
to its
i
th 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
∖
{
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
∖
{
v
}
]
is not CC.