Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-12T19:58:58.423Z Has data issue: false hasContentIssue false
  • English
  • Français

Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size

Published online by Cambridge University Press:  02 February 2012

CARLOS HOPPEN,
YOSHIHARU KOHAYAKAWA and
HANNO LEFMANN
CARLOS HOPPEN
Affiliation:
Instituto de Matemática, Universidade Federal do Rio Grande do Sul, Avenida Bento Gonçalves, 9500, 91509-900 Porto Alegre, Brazil (e-mail: choppen@ufrgs.br)
YOSHIHARU KOHAYAKAWA
Affiliation:
Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão, 1010, 05508-090, São Paulo, Brazil (e-mail: yoshi@ime.usp.br)
HANNO LEFMANN
Affiliation:
Fakultät für Informatik, Technische Universität Chemnitz, Straße der Nationen 62, D-09107 Chemnitz, Germany (e-mail: Lefmann@Informatik.TU-Chemnitz.de)
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.

Let k and ℓ be positive integers. With a graph G, we associate the quantity ck,ℓ(G), the number of k-colourings of the edge set of G with no monochromatic matching of size ℓ. Consider the function ck,ℓ: given by ck,ℓ(n) = max {ck,ℓ(G): |V(G)| = n}, the maximum of ck,ℓ(G) over all graphs G on n vertices. In this paper, we determine ck,ℓ(n) and the corresponding extremal graphs for all large n and all fixed values of k and ℓ.

Information

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

References

[1]Alon, N., Balogh, J., Keevash, P. and Sudakov, B. (2004) The number of edge colorings with no monochromatic cliques. J. London Math. Soc. (2) 70 273–288.Google Scholar
[2]Balogh, J. (2006) A remark on the number of edge colorings of graphs. Europ. J. Combin. 77 565–573.CrossRefGoogle Scholar
[3]Erdős, P. (1974) Some new applications of probability methods to combinatorial analysis and graph theory. In Proc. Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton 1974, Congressus Numerantium X 39–51.Google Scholar
[4]Erdős, P. and Gallai, T. (1959) On maximal paths and circuits. Acta Math. Acad. Sci. Hungar. 10 337–356.CrossRefGoogle Scholar
[5]Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.CrossRefGoogle Scholar
[6]Lefmann, H., Hoppen, C. and Kohayakawa, Y. (2011) Hypergraphs with many Kneser colorings. Europ. J. of Combin., doi:10.1016/j.ejc.2011.09.025 (in press).CrossRefGoogle Scholar
[7]Hoppen, C., Kohayakawa, Y. and Lefmann, H. Edge colorings of graphs avoiding some fixed monochromatic subgraph with linear Turán number. Electron. Notes Discrete Math. (Proc. EUROCOMB 2011), in press doi:10.1016/j.endm.2011.09.076.Google Scholar
[8]Lefmann, H. and Person, Y. Exact results on the number of restricted edge colorings for some families of linear hypergraphs. Submitted.Google Scholar
[9]Lefmann, H., Person, Y., Rödl, V. and Schacht, M. (2009) On colorings of hypergraphs without monochromatic Fano planes, Combin. Probab. Comput. 18 803–818.CrossRefGoogle Scholar
[10]Lefmann, H., Person, Y. and Schacht, M. (2010) A structural result for hypergraphs with many restricted edge colorings. J. Combin. 1 441–475.Google Scholar
[11]Pikhurko, O. and Yilma, Z. B. The maximum number of K 3-free and K 4-free edge 4-colorings. J. London Math. Soc., to appear.Google Scholar
[12]Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes: Colloq. Internat. CNRS, Orsay 1976, Vol. 260 of Colloq. Internat. CNRS, CNRS, pp. 399–401.Google Scholar
[13]Yuster, R. (1996) The number of edge colorings with no monochromatic triangle. J. Graph Theory 21 441–452.Google Scholar