✦ LIBER ✦

The rainbow number of matchings in regular bipartite graphs

✍ Scribed by Xueliang Li; Zhixia Xu

Publisher: Elsevier Science
Year: 2009
Tongue: English
Weight: 386 KB
Volume: 22
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2009.03.019

No coin nor oath required. For personal study only.

✦ Synopsis

Given a graph G and a subgraph H of G, let rb(G, H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G, H) is called the rainbow number of H with respect to G. Denote as mK 2 a matching of size m and as B n,k the set of all the k-regular bipartite graphs with bipartition (X, Y ) such that | X |=| Y |= n and k ≤ n. Let k, m, n be given positive integers, where k ≥ 3, m ≥ 2 and n > 3(m-1). We show that for every G ∈ B n,k , rb(G, mK 2 ) = k(m -2) + 2. We also determine the rainbow numbers of matchings in paths and cycles.

📜 SIMILAR VOLUMES

Finding all the perfect matchings in bip

Finding all the perfect matchings in bipartite graphs

✍ K. Fukuda; T. Matsui 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 283 KB

Special parity of perfect matchings in b

Special parity of perfect matchings in bipartite graphs

✍ Ron Aharoni; Rachel Manber; Bronislaw Wajnryb 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 527 KB

Let G be a bipartite graph in which every edge belongs to some perfect matching, and let D be a subset of its edge set. It is shown that M fl D has the same parity for every perfect matching M if and only if D is a cut, and equivalently if and only. if (G, D) is a balanced signed-graph. This gives n

The total chromatic number of regular gr

The total chromatic number of regular graphs whose complement is bipartite

✍ J.K. Dugdale; A.J.W. Hilton 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 705 KB

We show that a regular graph G of order at least 6 whose complement c is bipartite has total chromatic number d(G) + 1 if and only if (i) G is not a complete graph, and (ii) G#K when n is even. As an aid in"';he proof of this, we also show that , for n>4, if the edges of a Hamiltonian path of Kzn a

On the bipartite independence number of

On the bipartite independence number of a balanced bipartite graph

✍ Odile Favaron; Pedro Mago; Oscar Ordaz 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 603 KB

Venezuela Ap. 47567, Caracas Favaron, O., P. Mago and 0. Ordaz, On the bipartite independence number of a balanced bipartite graph, Discrete Mathematics 121 (1993) 55-63. The bipartite independence number GI aIp of a bipartite graph G is the maximum order of a balanced independent set of G. Let 6 b

The most vital edges of matching in a bi

The most vital edges of matching in a bipartite graph

✍ Chun-Nan Hung; Lih-Hsing Hsu; Ting-Yi Sung 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB

The maximal number of induced complete b

The maximal number of induced complete bipartite graphs

✍ Béla Bollobás; Chiê Nara; Shun-ichi Tachibana 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 230 KB

The aim of this paper is to determine the maximal number of induced K(t, t) subgraphs in graphs of given order and in graphs of given size. Given a graph G and a natural number t, denote by ft(G) the number of induced subgraphs of G isomorphic to K(t, t). Our notation is that of ; in particular, K(