×

Stars and bonds in crossing-critical graphs. (English) Zbl 1267.05089

Ossona de Mendez, Patrice (ed.) et al., The international conference on topological and geometric graph theory. Papers from the conference (TGGT 2008) held at the École Normale Supérieure, Paris, France, May 19–23, 2008. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 31, 271-275 (2008).
Summary: The structure of all known infinite families of crossing-critical graphs has led to the conjecture that crossing-critical graphs have bounded bandwidth. If true, this would imply that crossing-critical graphs have bounded degree, that is, that they cannot contain subdivisions of \(K_{1,n}\) for arbitrarily large \(n\). In this paper we prove two results that revolve around this conjecture. On the positive side, we show that crossing-critical graphs cannot contain subdivisions of \(K_{2,n}\) for arbitrarily large \(n\). On the negative side, we show that there are graphs with arbitrarily large maximum degree that are 2-crossing-critical in the projective plane.
For the entire collection see [Zbl 1239.05009].

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] D. Bokal, Infinite families of crossing-critical graphs with prescribed average degree and crossing number; D. Bokal, Infinite families of crossing-critical graphs with prescribed average degree and crossing number
[2] Bokal, D.; Fijavz, G.; Mohar, B., The Minor Crossing Number, SIAM J. Discrete Mathematics, 20, 344-356 (2006) · Zbl 1118.05016
[3] Geelen, J.; Richter, B.; Salazar, G., Embedding grids in surfaces, Europ. J. Combinatorics, 25, 785-792 (2004) · Zbl 1050.05035
[4] Hliněný, P., Crossing-critical graphs and path-width, (Graph Drawing GD 2001. Graph Drawing GD 2001, Vienna Austria, September 2001. Graph Drawing GD 2001. Graph Drawing GD 2001, Vienna Austria, September 2001, Lecture Notes in Computer Science, 2265 (2002), Springer Verlag), 102-114 · Zbl 1054.68590
[5] Hliněný, P., Crossing-critical graphs have bounded path-width, J. of Combinatorial Theory ser. B, 88, 347-367 (2003) · Zbl 1021.05028
[6] P. Hliněný, New infinite families of almost-planar crossing-critical graphs; P. Hliněný, New infinite families of almost-planar crossing-critical graphs
[7] Kochol, M., Construction of crossing-critical graphs, Discrete Math., 66, 311-313 (1987) · Zbl 0618.05021
[8] R.B. Richter, G. Salazar, A Survey of Good Crossing Number Theorems and Questions; R.B. Richter, G. Salazar, A Survey of Good Crossing Number Theorems and Questions
[9] Richter, R. B.; Thomassen, C., Minimal graphs with crossing number at least \(k\), J. Combinatorial Theory Ser. B, 58, 217-224 (1993) · Zbl 0733.05035
[10] Salazar, G., Infinite families of crossing-critical graphs with given average degree, Discrete Math., 271, 343-350 (2003) · Zbl 1021.05029
[11] Širáň, J., Infinite families of crossing-critical graphs with a given crossing number, Discrete Math., 48, 129-132 (1984) · Zbl 0535.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.