|
Adam Idzik, Zsolt Tuza
Heredity Properties of Connectedness in
Edge-Coloured Complete Graphs
876
Abstract
If the monochromatic graphs G1 and G2
in a 2-edge-coloured complete graph Km
($m\geq 6$)
are connected, then there exist
at least two vertices $x$ such that the graphs $G^1\setminus x$ and
$G^2\setminus x$ are also connected. Similar theorems are proved
for $k$-edge-coloured complete graphs. They generalize earlier results
of Idzik, Komar and Malawski [Discr.\ Math.\ 66 (1987), 119--125].
Examples are shown that analogous theorems
are no longer true for $3$-uniform complete hypergraphs.
Key words:
Complete graph, connected graph,
edge-colouring, $r$-uniform hypergraph.
|
|
 |
 |
