𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonian chains in hypergraphs

✍ Scribed by Katona, Gyula Y.; Kierstead, H. A.

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
111 KB
Volume
30
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A cyclic ordering of the vertices of a k-uniform hypergraph is called a hamiltonian chain if any k consecutive vertices in the ordering form an edge. For k = 2 this is the same as a hamiltonian cycle. We consider several natural questions about the new notion. The main result is a Dirac-type theorem that provides a sufficient condition for finding hamiltonian chains in k-uniform hypergraphs with large (k -1)-minimal degree. If it is more than (1 -1 2k )n + 4 -k -5 2k , than the hypergraph contains a hamiltonian chain.

📜 SIMILAR VOLUMES

Monochromatic Hamiltonian t-tight Berge-
Monochromatic Hamiltonian t-tight Berge-cycles in hypergraphs
✍ Paul Dorbec; Sylvain Gravier; Gábor N. Sárközy 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB

## Abstract In any __r__‐uniform hypergraph ${\cal{H}}$ for 2 ≤ __t__ ≤ __r__ we define an __r__‐uniform __t__‐tight Berge‐cycle of length ℓ, denoted by __C__~ℓ~^(__r__, __t__)^, as a sequence of distinct vertices __v__~1~, __v__~2~, … , __v__~ℓ~, such that for each set (__v__~__i__~, __v__~__i__ +

Monochromatic Hamiltonian 3-tight Berge
Monochromatic Hamiltonian 3-tight Berge cycles in 2-colored 4-uniform hypergraphs
✍ András Gyárfás; Gábor N. Sárközy; Endre Szemerédi 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract Here improving on our earlier results, we prove that there exists an __n__~0~ such that for __n__⩾__n__~0~ in every 2‐coloring of the edges of __K__ there is a monochromatic Hamiltonian 3‐tight Berge cycle. This proves the __c__=2, __t__=3, __r__=4 special case of a conjecture from (P.

On the use of alternating chains and hyp
On the use of alternating chains and hypergraphs in edge coloring
✍ D. de Werra 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 320 KB

## Abstract Existence of some generalized edge colorings is proved by using the properties of hypergraphs as well as alternating chain methods. A general framework is given for edge colorings and some general properties of balancing are derived.

Nested Chain Partitions of Hamiltonian F
Nested Chain Partitions of Hamiltonian Filters
✍ David G.C. Horrocks 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 340 KB

Let P be a poset, consisting of all sets X [n]=[1, 2, ..., n] which contain at least one of a given collection F of 2-subsets of [n], ordered by inclusion. By modifying a construction of Greene and Kleitman, we show that if F is hamiltonian, that is, contains [1, 2], [2, 3], ..., [n&1, n] and [1, n]

Choosability in Random Hypergraphs
Choosability in Random Hypergraphs
✍ Michael Krivelevich; Van H. Vu 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 155 KB

The choice number of a hypergraph H=(V, E) is the least integer s for which, for every family of color lists S=[S(v): v # V], satisfying |S(v)|=s for every v # V, there exists a choice function f so that f (v) # S(v) for every v # V, and no edge of H is monochromatic under f. In this paper we consid

C-perfect hypergraphs
C-perfect hypergraphs
✍ Csilla Bujtás; Zsolt Tuza 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

## Abstract Let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{H}}=({{X}},{\mathcal{E}})$\end{document} be a hypergraph with vertex set __X__ and edge set \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{E}}$\end{document}. A C‐colori