Přejít k obsahu


Equivalence of Jackson's and Thomassen's conjectures

Citace:
ČADA, R., CHIBA, S., OZEKI, K., VRÁNA, P., YOSHIMOTO, K. Equivalence of Jackson's and Thomassen's conjectures. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, roč. 114, č. září, s. 124-147. ISSN: 0095-8956
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Equivalence of Jackson's and Thomassen's conjectures
Rok vydání: 2015
Autoři: Doc. Ing. Roman Čada Ph.D. , Shuya Chiba , Kenta Ozeki , Mgr. Petr Vrána Ph.D. , Kiyoshi Yoshimoto
Abstrakt CZ: Thomasenova hypotéza (1986) říká, že 4-souvislé hranové grafy jsou hamiltonovské. Zdánlivě slabší Jacksonova hypotéza (1992) tvrdí, že každý 2-souvislý graf bez K_{1,3} má Tutteovu kružnici. Je ukázáno, že obě hypotézy jsou ve skutečnosti ekvivalentní.
Abstrakt EN: Thomassen's conjecture (1986) says that 4-connected line graphs are hamiltonian. A seemingly weaker conjecture of Jackson (1992) states that every 2-connected claw-free graph has a Tutte cycle. It is shown that both conjectures are in fact equivalent.
Klíčová slova

Zpět

Patička