𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Rainbow and orthogonal paths in factorizations of Kn

✍ Scribed by András Gyárfás; Mehdi Mhalla

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
164 KB
Volume
18
Category
Article
ISSN
1063-8539

No coin nor oath required. For personal study only.

✦ Synopsis

For n even, a factorization of a complete graph K n is a partition of the edges into n-1 perfect matchings, called the factors of the factorization. With respect to a factorization, a path is called rainbow if its edges are from distinct factors. A rainbow Hamiltonian path takes exactly one edge from each factor and is called orthogonal to the factorization. It is known that not all factorizations have orthogonal paths. Assisted by a simple edge-switching algorithm, here we show that for n ≥ 8, the rotational factorization of K n , GK n has orthogonal paths. We prove that this algorithm finds a rainbow path with at least (2n+1)/3 vertices in any factorization of K n (in fact, in any proper coloring of K n ). We also give some problems and conjectures about the properties of the algorithm.

📜 SIMILAR VOLUMES

On tree factorizations of Kn
On tree factorizations of Kn
✍ Min-Li Yu 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 647 KB

## Abstract In this paper we exhibit a class of trees with the property that if __T__~__k__~ is a tree on __k__ vertices that belongs to this class, then necessary and sufficient conditions for __K__~__n__~ to have a __T__~__k__~‐factorization are simply __n__ = 0 (mod k) and __n__ = 1 (mod 2(__k__

Orthogonal factorizations of graphs
Orthogonal factorizations of graphs
✍ Haodi Feng; Guizhen Liu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract Let __G__ be a graph with vertex set __V__(__G__) and edge set __E__(__G__). Let __k__~1~, __k__~2~,…,__k__~m~ be positive integers. It is proved in this study that every [0,__k__~1~+…+__k__~__m__~−__m__+1]‐graph __G__ has a [0, __k__~i~]~1~^__m__^‐factorization orthogonal to any given

Orthogonal (g, f)-factorizations in netw
Orthogonal (g, f)-factorizations in networks
✍ Peter Che Bor Lam; Guizhen Liu; Guojun Li; Wai Chee Shiu 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB 👁 1 views

Let G G G = (V V V, E E E) be a graph and let g g g and f f f be two integervalued functions defined on V V V such that k k k ≤ ≤ ≤ g g g(x x x) ≤ ≤ ≤ f f f(x x x) for all x x x ∈ ∈ ∈ V

On bipartite 2-factorizations of kn − I
On bipartite 2-factorizations of kn − I and the Oberwolfach problem
✍ Darryn Bryant; Peter Danziger 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB

It is shown that if F 1 , F 2 , ...,F t are bipartite 2-regular graphs of order n and 1 , 2 , . . . , t are positive integers such that 1 + 2 +• • •+ t = (n-2) / 2, 1 ≥ 3 is odd, and i is even for i = 2, 3, . . . , t, then there exists a 2-factorization of K n -I in which there are exactly i 2-facto

On the existence of a rainbow 1-factor i
On the existence of a rainbow 1-factor in 1-factorizations of K
✍ S.I. El-Zanati; M.J. Plantholt; P.A. Sissokho; L.E. Spence 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 85 KB 👁 1 views

## Abstract Let ${\cal F}$ be a 1‐factorization of the complete uniform hypergraph ${\cal G}={K\_{rn}^{(r)}}$ with $r \geq 2$ and $n\geq 3$. We show that there exists a 1‐factor of ${\cal G}$ whose edges belong to __n__ different 1‐factors in ${\cal F}$. Such a 1‐factor is called a “rainbow” 1‐fact