New infinite families of almost-planar crossing-critical graphs

• Název česky: Nové nekonečné třídy téměř planárních průsečíkově kritických grafů
• Autoři: HLINĚNÝ Petr
• Rok publikování: 2008
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Electronic Journal of Combinatorics
• Fakulta / Pracoviště MU: Fakulta informatiky
• www: online paper
• Obor: Obecná matematika
• Klíčová slova: crossing-critical; graph
• Popis: Ukážeme konstrukci jednoduchých 3-souvislých k-průsečíkově kritických grafů, které obsahují libovolně mnoho vrcholů sudých stupňů <=2k-2 pro všechna k>2. Tato konstrukce zodpovídá jednu polovinu otázky Bokala a má několik dalších zajímavých aplikací.

Související projekty

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