Geodesic
On the sharpness of some results relating cuts and crossing numbers
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

It is already known that for very small edge cuts in graphs, the crossing number of the graph is at least the sum of the crossing number of (slightly augmented) components resulting from the cut. Under stronger connectivity condition in each cut component that was formalized as a graph operation called zip product, a similar result was obtained for edge cuts of any size, and a natural question was asked, whether this stronger condition is necessary. In this paper, we prove that the relaxed condition is not sufficient when the size of the cut is at least four, and we prove that the gap can grow quadratically with the cut size.
DOI : 10.37236/368
Classification : 05C10, 05C40
Mots-clés : connectivity condition 
@article{10_37236_368,
     author = {Laurent Beaudou and Drago Bokal},
     title = {On the sharpness of some results relating cuts and crossing numbers},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/368},
     zbl = {1230.05106},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/368/}
}
TY  - JOUR
AU  - Laurent Beaudou
AU  - Drago Bokal
TI  - On the sharpness of some results relating cuts and crossing numbers
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/368/
DO  - 10.37236/368
ID  - 10_37236_368
ER  - 
%0 Journal Article
%A Laurent Beaudou
%A Drago Bokal
%T On the sharpness of some results relating cuts and crossing numbers
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/368/
%R 10.37236/368
%F 10_37236_368
Laurent Beaudou; Drago Bokal. On the sharpness of some results relating cuts and crossing numbers. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/368

Cité par Sources :