Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T09:52:26.005Z Has data issue: false hasContentIssue false
  • English
  • Français

Monochromatic Cycles in 2-Coloured Graphs

Published online by Cambridge University Press:  19 March 2012

F. S. BENEVIDES ,
T. ŁUCZAK ,
A. SCOTT ,
J. SKOKAN  and
M. WHITE
F. S. BENEVIDES
Affiliation:
Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Ceará, Brazil, 60455-760 (e-mail: fabricio@mat.ufc.br)
T. ŁUCZAK
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, 61-614 Poznań, Poland (e-mail: tomasz@amu.edu.pl)
A. SCOTT*
Affiliation:
Mathematical Institute, 24–29 St Giles', Oxford, OX1 3LB, UK (e-mail: scott@maths.ox.ac.uk, white@maths.ox.ac.uk)
J. SKOKAN
Affiliation:
Department of Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK (e-mail: jozef@member.ams.org)
M. WHITE
Affiliation:
Mathematical Institute, 24–29 St Giles', Oxford, OX1 3LB, UK (e-mail: scott@maths.ox.ac.uk, white@maths.ox.ac.uk)
*
§Corresponding author.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Li, Nikiforov and Schelp [13] conjectured that any 2-edge coloured graph G with order n and minimum degree δ(G) > 3n/4 contains a monochromatic cycle of length ℓ, for all ℓ ∈ [4, ⌈n/2⌉]. We prove this conjecture for sufficiently large n and also find all 2-edge coloured graphs with δ(G)=3n/4 that do not contain all such cycles. Finally, we show that, for all δ>0 and n>n0(δ), if G is a 2-edge coloured graph of order n with δ(G) ≥ 3n/4, then one colour class either contains a monochromatic cycle of length at least (2/3+δ/2)n, or contains monochromatic cycles of all lengths ℓ ∈ [3, (2/3−δ)n].

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 57 - 87
Copyright
Copyright © Cambridge University Press 2012

References

[1]Benevides, F. and Skokan, J. (2009) The 3-colored Ramsey number of even cycles. J. Combin. Theory Ser. B 99 690–708.CrossRefGoogle Scholar
[2]Berge, C. (1958) Sur le couplage maximum d'un graphe (in French). CR Acad. Sci. Paris 247 258–259.Google Scholar
[3]Bollobás, B. (1978) Extremal Graph Theory, Academic Press.Google Scholar
[4]Bollobás, B., Benevides, F., Łuczak, T. and Skokan, J. (2011) Graphs with large minimum degrees arrow even cycles. Manuscript.Google Scholar
[5]Bondy, J. (1971) Pancyclic graphs I. J. Combin. Theory Ser. B 11 80–84.CrossRefGoogle Scholar
[6]Bondy, J. and Simonovits, M. (1974) Cycles of even lengths in graphs. J. Combin. Theory Ser. B 16 97–105.CrossRefGoogle Scholar
[7]Chvátal, V. (1972) On Hamilton's ideals. J. Combin. Theory Ser. B 12 163–168.CrossRefGoogle Scholar
[8]Dirac, G. (1952) Some theorems on abstract graphs. Proc. London Math. Soc. 2 69–81.CrossRefGoogle Scholar
[9]Erdős, P. and Gallai, T. (1959) On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. 10 337–356.CrossRefGoogle Scholar
[10]Gyárfás, A. and Sárközy, G. N. (2012) Star versus two stripes Ramsey numbers and a conjecture of Schelp. Combin. Prob. Comput. 21 179–186.CrossRefGoogle Scholar
[11]Győri, E., Nikiforov, V. and Schelp, R. (2003) Nearly bipartite graphs. Disc. Math. 272 187–196.CrossRefGoogle Scholar
[12]Komlós, J. and Simonovits, M. (1996) Szemerédi's regularity lemma and its applications in graph theory. In Combinatorics: Paul Erdős is Eighty, Vol. 2 of Bolyai Society Mathematical Studies, pp. 295–352.Google Scholar
[13]Li, H., Nikiforov, V. and Schelp, R. (2010) A new type of Ramsey–Turán problems. Disc. Math. 310 3579–3583.CrossRefGoogle Scholar
[14]Szemerédi, E. (1976) Regular partitions of graphs. Colloques Internationaux CNRS: Problèmes Combinatoires et Théorie des Graphes 260 399–401.Google Scholar
[15]Tutte, W. (1947) A factorization of linear graphs. J. London Math. Soc. 22 107–111.CrossRefGoogle Scholar