𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Existence of Exactlym-Coloured Complete Subgraphs

✍ Scribed by Alan Stacey; Peter Weidl

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
842 KB
Volume
75
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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 exists an infinite complete subgraph of K | whose edges are exactly m-coloured. Ramsey's Theorem states that P(c, m) is true for m=1 and all c 1, and can easily be used to show that P(c, m) holds when m=2 and c 2. Erickson conjectured that P(c, m) is false whenever c>m 3. We prove that given m 3 there exists an integer C(m) such that P(c, m) is false for all c C(m).

πŸ“œ SIMILAR VOLUMES

Edge-coloured complete graphs: Connected
Edge-coloured complete graphs: Connectedness of some subgraphs
✍ Adam Idzik; Jan Komar; Marcin Malawski πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 435 KB

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 f

Bounds on the number of complete subgrap
Bounds on the number of complete subgraphs
✍ David C. Fisher; Jennifer Ryan πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 385 KB

Fisher, D.C. and J. Ryan, Bounds on the number of complete subgraphs, Discrete Mathematics 103 (1992) 313-320. Let G be a graph with a clique number w. For 1 s s w, let k, be the number of complete j subgraphs on j nodes. We show that k,,, c (j~l)(kj/(~))u""'. This is exact for complete balanced w-

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

Forbidden subgraphs and the existence of
Forbidden subgraphs and the existence of a 2-factor
✍ R. E. L. Aldred; Jun Fujisawa; Akira Saito πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 195 KB πŸ‘ 1 views

## Abstract In this paper, we consider forbidden subgraphs which force the existence of a 2‐factor. Let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}$\end{document} be the class of connected graphs of minimum degree at least two and maximum degree at least three, an