Další formáty:
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 a 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, s.~''14:1''-''14:15'', 15 s. ISBN~978-3-95977-104-7. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14.
|