✦ LIBER ✦

Partitioning Complete Bipartite Graphs by Monochromatic Cycles

✍ Scribed by P.E. Haxell

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 886 KB
Volume: 69
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1737

No coin nor oath required. For personal study only.

✦ Synopsis

For every positive integer r there exists a constant C r depending only on r such that for every colouring of the edges of the complete bipartite graph K n, n with r colours, there exists a set of at most C r monochromatic cycles whose vertex sets partition the vertex set of K n, n . This answers a question raised by Erdo s, Gya rfa s, and Pyber.

📜 SIMILAR VOLUMES

Partitioning complete multipartite graph

Partitioning complete multipartite graphs by monochromatic trees

✍ Atsushi Kaneko; M. Kano; Kazuhiro Suzuki 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

The tree partition number of an r-edge-colored graph G, denoted by t r (G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex-disjoint monochromatic trees. We determine t 2 (K (n 1 ; n 2 ; . . . ; n k )) of the c

Monochromatic cycle partitions of edge-c

Monochromatic cycle partitions of edge-colored graphs

✍ Gábor N. Sárközy 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB 👁 1 views

In this article we study the monochromatic cycle partition problem for non-complete graphs. We consider graphs with a given independence number (G) = . Generalizing a classical conjecture of Erd" os, Gyárfás and Pyber, we conjecture that if we r-color the edges of a graph G with (G) = , then the ver

Partition of a bipartite graph into cycl

Partition of a bipartite graph into cycles

✍ Hong Wang 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 241 KB

Wang, H., Partition of bipartite graph into cycles, Discrete Mathematics 117 (1993) 287-291. El-Zahar (1984) conjectured that if G is a graph on n, + n, + + nk vertices with ni > 3 for 1s i < k and minimum degree 6(G)>rn,/21+rn2/21+ ... +rn,/21, then G contains k vertex-disjoint cycles of lengths n,

Alternating hamiltonian cycles in two co

Alternating hamiltonian cycles in two colored complete bipartite graphs

✍ A. G. Chetwynd; A. J. W. Hilton 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 2 views

## Abstract We give necessary and sufficient conditions for the existence of an alternating Hamiltonian cycle in a complete bipartite graph whose edge set is colored with two colors.

Partition of a bipartite hamiltonian gra

Partition of a bipartite hamiltonian graph into two cycles

✍ Denise Amar 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 480 KB

We prove the following theorem. "I'neorem. If G is a balanced bipartite graph with bipartition (A, B), [A I = IBI = n, such that for any x ~ A, y ~ B, d(x) + d(y) >>-n + 2, then for any (nl, n2), ni >I 2, n -----n I + hE, G contains two independent cycles of lengths 2nl and 2n2.

Partition of a directed bipartite graph

Partition of a directed bipartite graph into two directed cycles

✍ Hong Wang; Charles Little; Kee Teo 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 356 KB

Let D = (V1, V2; A) be a directed bipartite graph with II/11 = 11/21 = n ~> 2. Suppose that do(x) + do(y) >~ 3n + 1 for all xe I/1 and ye V2. Then D contains two vertex-disjoint directed cycles of lengths 2nl and 2n2, respectively, for any positive integer partition n = n~ + n2. Moreover, the condit