On a new reformulation of Hadwiger's conjecture

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00005543" target="_blank" >RIV/00216208:11320/06:00005543 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
On a new reformulation of Hadwiger's conjecture
Original language description
Assuming that every proper minor closed class of graphs contains a maximum with respect to the homomorphism order, we prove that such a maximum must be homomorphically equivalent to a complete graph. This proves that Hadwiger's conjecture is equivalent to saying that every minor closed class of graphs contains a maximum with respect to homomorphism order. Let F be a finite set of 2-connected graphs, and let C be the class of graphs with no minor from F. We prove that if C has a maximum, then any maximumof C must be homomorphically equivalent to a complete graph. This is a special case of a conjecture of Nesetril and Ossona de Mendez.
Czech name
O novém přeformulování Hadwigerovy hypotézy
Czech description
Za předpokladu, že každá minorově uzavřená třída grafů má maximum v homomorfismovém uspořádání, dokážeme, že takové maximum musí být homomorficky ekvivalentní úplnému grafu. To dokazuje, že Hadwigerova hypotéza je ekvivalentní tvrzení, že každá minorověuzavřená třída grafů má maximum v homomorfismovém uspořádání. Nechť F je konečná množina 2-souvislých grafů, nechť C je třída grafů, které nemají minor patřící do F. Dokážeme, že pokud C má maximum, pak každé maximum je homomorficky ekvivalentní úplnémugrafu. To je speciální případ hypotézy Nešetřila a Ossony de Mendez.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)