×

Rainbows in the hypercube. (English) Zbl 1118.05028

Authors’ abstract: Let \(Q_n\) be a hypercube of dimension \(n\), that is, a graph whose vertices are binary \(n\)-tuples and two vertices are adjacent if and only if the corresponding \(n\)-tuples differ in exactly one position. An edge coloring of a graph \(H\) is called rainbow if no two edges of \(H\) have the same color. Let \(f (G, H)\) be the largest number of colors such that there exists an edge coloring of \(G\) with \(f(G, H)\) colors such that no subgraph isomorphic to \(H\) is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on \(f(Q_n, Q_k)\) which are asymptotically tight for \(k = 2\) and by giving some exact results.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Axenovich, M., Jiang, T., Kündgen, A.: Bipartite anti-Ramsey numbers of cycles and path covers in bipartite graphs. J. Graph Theory 47, 9–28 (2004) · Zbl 1062.05095
[2] Axenovich, M., Jiang, T.: Anti-Ramsey numbers for small complete bipartite graphs, Ars Combin. 73, 311–318 (2004) · Zbl 1072.05041
[3] Chung, F.R.K.: Subgraphs of a hypercube containing no small even cycles. J. Graph Theory 16, 273–286 (1992) · Zbl 0766.05039
[4] Erdos, P., Simonovits, M., Sós, V.T.: Anti-Ramsey theorems, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to Erdos P. on his 60th birthday), Vol. II, pp. 633–643. Colloq. Math. Soc. Janos Bolyai, Vol. 10, North-Holland, Amsterdam, 1975
[5] Haxell, P.E., Kohayakawa, Y.: On an anti-Ramsey property of Ramanujan graphs, Random Structures Algorithms 6, 417–1431 (1995) · Zbl 0830.05047
[6] Jiang, T., West, D.B.: Edge-colorings of complete graphs that avoid polychromatic trees. Discrete Math. 274(1–3), 137–145 (2004) · Zbl 1032.05089
[7] Montellano-Ballesteros, J.J., Neumann-Lara, V.: An anti-Ramsey theorem. Combinatorica 22, 445–449 (2002) · Zbl 1012.05092
[8] Schiermeyer, I.: Rainbow 5- and 6-cycles: A proof of the conjecture of Erdos, Simonovits and Sós, preprint, TU Bergakademie Freiberg, 2001
[9] Schiermeyer, I.: Rainbow Colourings. Notices of the South African Mathematical Society 34, 51–59 (2003)
[10] Schiermeyer, I.: Rainbow Numbers for Matchings and Complete Graphs. Discrete Mathematics 286, 157–162 (2004) · Zbl 1053.05053
[11] West, D.B.: Introduction to Graph Theory, 2nd edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 2001 · Zbl 0992.83079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.