✦ LIBER ✦

Bipartite anti-Ramsey numbers of cycles

✍ Scribed by Maria Axenovich; Tao Jiang; André Kündgen

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 265 KB
Volume: 47
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20012

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We determine the maximum number of colors in a coloring of the edges of K~m,n~ such that every cycle of length 2__k__ contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers q≤ a, let g(a,q) be the maximum number of edges in a spanning subgraph G of K~a,a~ such that the minimum number of vertex‐disjoint even paths and pairs of vertices from distinct partite sets needed to cover V(G) is q. We prove that g(a,q) = a^2^ − aq + max {a, 2__q__ − 2}. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 9–28, 2004

📜 SIMILAR VOLUMES

Multipartite Ramsey numbers for odd cycl

Multipartite Ramsey numbers for odd cycles

✍ András Gyárfás; Gábor N. Sárközy; Richard H. Schelp 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB

## Abstract In this paper we study multipartite Ramsey numbers for odd cycles. We formulate the following conjecture: Let __n__≥5 be an arbitrary positive odd integer; then, in any two‐coloring of the edges of the complete 5‐partite graph __K__((__n__−1)/2, (__n__−1)/2, (__n__−1)/2, (__n__−1)/2, 1)

Anti-Ramsey Numbers of Subdivided Graphs

✍ Tao Jiang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 88 KB

Given a positive integer n and a family F of graphs, the anti-Ramsey number f(n, F) is the maximum number of colors in an edge-coloring of K n such that no subgraph of K n belonging to F has distinct colors on its edges. The Tura ´n number ex(n, F) is the maximum number of edges of an n-vertex graph

On the multi-colored Ramsey numbers of c

On the multi-colored Ramsey numbers of cycles

✍ Tomasz Łuczak; Miklós Simonovits; Jozef Skokan 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB

For a graph L and an integer k ≥ 2, R k (L) denotes the smallest integer N for which for any edge-coloring of the complete graph K N by k colors there exists a color i for which the corresponding color class contains L as a subgraph.

The characterization of zero-sum (mod 2)

The characterization of zero-sum (mod 2) bipartite Ramsey numbers

✍ Caro, Yair; Yuster, Raphael 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

Let G be a bipartite graph, with k|e(G). The zero-sum bipartite Ramsey number B(G, Z k ) is the smallest integer t such that in every Z k -coloring of the edges of K t,t , there is a zero-sum mod k copy of G in K t,t . In this article we give the first proof that determines B(G, Z 2 ) for all possib

Anti-Ramsey numbers of doubly edge-criti

Anti-Ramsey numbers of doubly edge-critical graphs

✍ Tao Jiang; Oleg Pikhurko 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract Given a graph __H__ and a positive integer __n__, __Anti‐Ramsey number AR__(__n, H__) is the maximum number of colors in an edge‐coloring of __K__~__n__~ that contains no polychromatic copy of __H__. The anti‐Ramsey numbers were introduced in the 1970s by Erdős, Simonovits, and Sós, who

Multicolor bipartite Ramsey number of C4

Multicolor bipartite Ramsey number of C4 and large Kn, n

✍ Qizhong Lin; Yusheng Li 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

Let br k (C 4 ; K n,n ) be the smallest N such that if all edges of K N,N are colored by k +1 colors, then there is a monochromatic C 4 in one of the first k colors or a monochromatic K n,n in the last color. It is shown that br k (C 4 ; K n,n ) = (n 2 / log 2 n) for k ≥ 3, and br 2 (C 4 ; K n,n ) ≥