Stars and Bonds in Crossing-Critical Graphs

• Název česky: Hvězdy a řezy v průsečíkově kritických grafech
• Autoři: HLINĚNÝ Petr; SALAZAR Gelasio
• Rok publikování: 2008
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Electronic Notes in Discrete Mathematics
• Fakulta / Pracoviště MU: Fakulta informatiky

www

• DOI
• conference

• Obor: Obecná matematika
• Klíčová slova: crossing number; crossing-critical graph
• Popis: Prezentujeme dva přístupy k dosud otevřené domněnce, že průsečíkově kritické grafy mají omezený maximální stupeň. Na pozitivní straně dokazujeme, že tyto grafy nemohou obsahovat subdivizi velkého K_2,n, ale na negativní straně ukazujeme neplatnost domněnky v projektivní rovině.

Související projekty

• Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti