𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Edge-coloured complete graphs: Connectedness of some subgraphs

✍ Scribed by Adam Idzik; Jan Komar; Marcin Malawski

Publisher
Elsevier Science
Year
1987
Tongue
English
Weight
435 KB
Volume
66
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

If the edges of a complete graph K,., m/> 4, are painted two colours so that monochromatic K " graphs are connected, then there exists an increasing sequence ( n)n~4 of complete subgraphs whose monochromatic subgraphs are also connected. For more than two colours this is not true, but an analogous fact concerning the complements of monochromatic graphs is proved. It is also shown that the theorems generalize to graphs with multicoloured edges, and some investigations of infinite complete graphs are made.

πŸ“œ SIMILAR VOLUMES

The Existence of Exactlym-Coloured Compl
The Existence of Exactlym-Coloured Complete Subgraphs
✍ Alan Stacey; Peter Weidl πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 842 KB

Given a graph G, its edges are said to be exactly x-coloured if we have a surjective map from the edges to some set of colours of size x. Erickson considered the following statement which he denoted P(c, m): if the edges of K | the complete graph on vertex set N are exactly c-coloured, then there ex

On complete subgraphs of color-critical
On complete subgraphs of color-critical graphs
✍ Xiang-Ying Su πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 488 KB

A graph G is called k-critical if x(G) = k and x(G -e) -C x(G) for each edge e of G, where x denotes the chromatic number. T. Gallai conjectured that every k-critical graph of order n contains at most n complete (kl)-subgraphs. In 1987, Stiebitz proved Gallai's conjecture in the case k = 4, and in 1

On complete subgraphs of r-chromatic gra
On complete subgraphs of r-chromatic graphs
✍ B. BollobΓ‘s; P. ErdΓΆs; E. SzemerΓ©di πŸ“‚ Article πŸ“… 1975 πŸ› Elsevier Science 🌐 English βš– 518 KB
Spanning even subgraphs of 3-edge-connec
Spanning even subgraphs of 3-edge-connected graphs
✍ Bill Jackson; Kiyoshi Yoshimoto πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 344 KB

## Abstract By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connec

Complete subgraphs of the graphs of conv
Complete subgraphs of the graphs of convex polytopes
✍ S. Gallivan; E.R. Lockeberg; P. McMullen πŸ“‚ Article πŸ“… 1981 πŸ› Elsevier Science 🌐 English βš– 631 KB

It is shown that if three vertices of the graph c?(l)) of a convex 3-polytope P are chosen, then G(P) contains a refinement of the complete graph C,, on four vertices, for which the three chosen vertices are principal (that is, correspond to vertices of C, in the refinement.. In general, all four ve