Další formáty:
BibTeX
LaTeX
RIS
@article{769706,
author = {Hliněný, Petr and Salazar, Gelasio},
article_number = {1},
keywords = {crossing number; crossing-critical graph},
language = {eng},
issn = {1571-0653},
journal = {Electronic Notes in Discrete Mathematics},
title = {Stars and Bonds in Crossing-Critical Graphs},
url = {http://tggt.cams.ehess.fr/},
volume = {31},
year = {2008}
}
TY - JOUR
ID - 769706
AU - Hliněný, Petr - Salazar, Gelasio
PY - 2008
TI - Stars and Bonds in Crossing-Critical Graphs
JF - Electronic Notes in Discrete Mathematics
VL - 31
IS - 1
SP - 271-275
EP - 271-275
PB - Elsevier
SN - 15710653
KW - crossing number
KW - crossing-critical graph
UR - http://tggt.cams.ehess.fr/
N2 - 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.
ER -
HLINĚNÝ, Petr a Gelasio SALAZAR. Stars and Bonds in Crossing-Critical Graphs. \textit{Electronic Notes in Discrete Mathematics}. Elsevier, 2008, roč.~31, č.~1, s.~271-275. ISSN~1571-0653.
|
