Monochromatic Hamiltonian Berge-cycles in colored hypergraphs
Autor: | Leila Maherani, Gholamreza Omidi |
---|---|
Rok vydání: | 2017 |
Předmět: |
Discrete mathematics
Hypergraph Conjecture 010102 general mathematics 0102 computer and information sciences 01 natural sciences Theoretical Computer Science Open case Combinatorics symbols.namesake Colored 010201 computation theory & mathematics symbols Discrete Mathematics and Combinatorics Monochromatic color 0101 mathematics Hamiltonian (quantum mechanics) Mathematics |
Zdroj: | Discrete Mathematics. 340:2043-2052 |
ISSN: | 0012-365X |
DOI: | 10.1016/j.disc.2016.09.032 |
Popis: | It has been conjectured that for any fixed r and sufficiently large n, there is a monochromatic Hamiltonian Berge-cycle in every (r1)-coloring of the edges of Knr, the complete r-uniform hypergraph on n vertices. In this paper, we show that the statement of this conjecture is true with r2 colors (instead of r1 colors) by showing that there is a monochromatic Hamiltonian t-tight Berge-cycle in every r2t1-edge-coloring of Knr for any fixed r>t2 and sufficiently large n. Also, we give a proof for this conjecture when r=4 (the first open case). These results improve the previously known results inDorbec et al. (2008) and Gyrfs et al. (2008, 2010). |
Databáze: | OpenAIRE |
Externí odkaz: |