New almost-planar crossing-critical graph families

HLINĚNÝ, Petr. New almost-planar crossing-critical graph families. In 6th Slovenian International Conference on Graph Theory. 2007. ISBN 978-961-212-198-3.

Základní údaje

• Originální název: New almost-planar crossing-critical graph families
• Název česky: Nove temer planarni prusecikove kriticke grafy
• Autoři: HLINĚNÝ, Petr (203 Česká republika, garant).
• Vydání: 6th Slovenian International Conference on Graph Theory, 2007.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Konferenční abstrakt
• Obor: 10101 Pure mathematics
• Stát vydavatele: Slovinsko
• Utajení: není předmětem státního či obchodního tajemství
• WWW: conference
• Kód RIV: RIV/00216224:14330/07:00024653
• Organizační jednotka: Fakulta informatiky
• ISBN: 978-961-212-198-3
• Klíčová slova anglicky: graph; crossing number; crossing-critical
• Štítky: crossing number, crossing-critical, graph
• Příznaky: Mezinárodní význam

Anotace

We show that, for all choices of integers $k>2$ and $m$, there are simple $3$-connected $k$-crossing-critical graphs containing more than $m$ vertices of each even degree $\leq2k-2$. This construction answers one half of a question raised by Bokal, while the other half asking analogously about vertices of odd degrees at least $5$ in crossing-critical graphs remains open. Furthermore, our constructed graphs have several other interesting properties; for instance, they are almost planar and their average degree can attain any rational value in the interval $\big[4,6-\frac8{k+1}\big)$.

Anotace česky

Konstuhujeme k-prusecikove kriticke grafy obsahujici libovolne mnoho vrcholu kazdeho sudeho stupne.

Návaznosti

• GA201/05/0050, projekt VaV: Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů