New infinite families of almost-planar crossing-critical graphs
type: Item
instance of: scholarly article
title: New infinite families of almost-planar crossing-critical graphs
zbMATH Open document ID: 1165.05322
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/130281
full work available at URL: v15i1r102.html
review text: Summary: 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 7 in crossing-critical graphs remains open. Furthermore, our newly 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 \([3+\frac{1}{5},6-\frac{8}{k+1})\).
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 5541007
zbMATH Keywords: crossing critical graphs
zbMATH Keywords: almost planar graphs
zbMATH Keywords: average degree
author: Petr Hliněný
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5541007