Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1646176,
author = {Bokal, Drago and Dvořák, Zdeněk and Hliněný, Petr and Leanos, Jesus and Mohar, Bojan and Wiedera, Tilo},
address = {Dagstuhl},
booktitle = {35th International Symposium on Computational Geometry, SoCG 2019},
doi = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14},
keywords = {Crossing number; Crossing-critical; Exhaustive generation; Path-width},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Dagstuhl},
isbn = {978-3-95977-104-7},
pages = {"14:1"-"14:15"},
publisher = {Leibniz International Proceedings in Informatics, LIPIcs},
title = {Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12},
url = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14},
year = {2019}
}
TY - JOUR
ID - 1646176
AU - Bokal, Drago - Dvořák, Zdeněk - Hliněný, Petr - Leanos, Jesus - Mohar, Bojan - Wiedera, Tilo
PY - 2019
TI - Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12
PB - Leibniz International Proceedings in Informatics, LIPIcs
CY - Dagstuhl
SN - 9783959771047
KW - Crossing number
KW - Crossing-critical
KW - Exhaustive generation
KW - Path-width
UR - http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14
N2 - We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c >= 13 and d >= 1, we give first explicit constructions of c-crossing-critical graphs containing a vertex of degree greater than d. We also show that such unbounded degree constructions do not exist for c <=12, precisely, that there exists a constant D such that every c-crossing-critical graph with c <=12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvorák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.
ER -
BOKAL, Drago, Zdeněk DVOŘÁK, Petr HLINĚNÝ, Jesus LEANOS, Bojan MOHAR and Tilo WIEDERA. Bounded degree conjecture holds precisely for c-crossing-critical graphs with c\&{}lt;=12. Online. In \textit{35th International Symposium on Computational Geometry, SoCG 2019}. Dagstuhl: Leibniz International Proceedings in Informatics, LIPIcs, 2019, p.~''14:1''-''14:15'', 15 pp. ISBN~978-3-95977-104-7. Available from: https://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14.
|
