Discussiones Mathematicae Graph Theory 25(1-2) (2005) 217-218
doi: 10.7151/dmgt.1274

[BIBTex] [PDF] [PS]


Adam Idzik

Akademia Świetokrzyska
15 Świetokrzyska street, 25-406 Kielce, Poland
Institute of Computer Science
Polish Academy of Sciences
21 Ordona street, 01-237 Warsaw, Poland
e-mail: adidzik@ipipan.waw.pl

All graphs considered here are finite simple graphs, i.e., graphs without loops, multiple edges or directed edges. For a graph G = (V,E), where V is a vertex set and E is an edge set, we write sometimes V(G) for V and E(G) for E to avoid ambiguity. We shall write G∖v instead of GV∖{v} = (V∖{v},E∩2V∖{v}), the subgraph induced by V∖{v}. A vertex v ∈ V(G) is called a cut-vertex of G if G is connected and G∖v is not. By a k-edge-colouring of a graph we mean any finite partition of the set of its edges into k subsets. A graph (V,E) with a given k-edge-colouring (E1,…,Ek) (Ei∩Ej = ∅ for i ± j; i,j ∈ {1,…,k} and ∪i ∈ {1,…,k} Ei = E) is denoted by (V,E1,…,Ek). The graphs (V,Ei) are called monochromatic subgraphs of (V,E1,…,Ek), i ∈ {1,…,k}. As usual, by Km we denote the complete graph with m vertices.

     Let c(Gi) denote the number of cut-vertices of Gi in a monochromatic subgraph Gi = (V,Ei) of a k-edge-coloured complete graph Km = (V,E1, …,Ek)  (i ∈ {1,…,k}).

     Given a k-edge-coloured graph G = (V,E1, …,Ek), we define Fi = E∖Ei, Gi = (V,Ei), Gi = (V,Fi), where E = ∪ i ∈ {1,… ,k} Ei and i ∈ {1,…,k}. Here Gi is a monochromatic subgraph of G and G i its complement in G.

Theorem (Idzik, Tuza, Zhu). Let (E1,… ,Ek) be a k-edge-colouring of Km (k ≥ 2, m ≥ 4), such that all the graphs G1,… ,Gk are connected.

(i) If one of the subgraphs G1,…,Gk is 2-connected, say Gi, then c(Gi) ≤ m −2 and c(G j) = 0 for j ± i (i,j ∈ {1,...,k}).
(ii) If none of the graphs G1,…, Gk is 2-connected, and one of them is connected, say Gi, then c(Gi) ≤ 2 (i ∈ {1,…,k}).

(iii) If none of the graphs G1,…,Gk is 2-connected, and one of them is disconnected, say Gi, then c(Gi) ≤ 1 (i ∈ {1,…,k}).
Problem. Let (E1,…, Ek) be a k-edge-colouring of Km(k ≥ 2, m ≥ 4). What is the cardinality of the set of the sum of cut-vertices of Gi in the case none of Gi is 2-connected and (a) two of Gi are connected or (b) two of Gi are disconnected and c(Gi) = 1 (i ∈ {1,…,k}) ?

Observe that in both cases (a) and (b) all the graphs G 1,…,Gk are connected.

     This problem is related to some theorems presented in [1] and [2].


[1] J. Bosák, A. Rosa and S. Znám, On decompositions of complete graphs into factors with given diameters, in: P. Erdős and G. Katona, eds., Theory of Graphs, Proceedings of the Colloquium Held at Tihany, Hungary (Academic Press, New York, 1968) 37-56.
[2] A. Idzik and Z. Tuza, Heredity properties of connectedness in edge-coloured complete graphs, Discrete Math. 235 (2001) 301-306, doi: 10.1016/S0012-365X(00)00282-X.

Received 21 November 2003