Premium
Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree
Author(s) -
GarciaMoreno Enrique,
Salazar Gelasio
Publication year - 2001
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200103)36:3<168::aid-jgt1004>3.0.co;2-#
Subject(s) - mathematics , crossing number (knot theory) , combinatorics , bounding overwatch , degree (music) , graph , discrete mathematics , computer science , physics , intersection (aeronautics) , artificial intelligence , acoustics , engineering , aerospace engineering
We show that if G has a minor M with maximum degree at most 4, then the crossing number of G in a surface Σ is at least one fourth the crossing number of M in Σ. We use this result to show that every graph embedded on the torus with representativity r ≥ 6 has Klein bottle crossing number at least ⌊2r/3⌋ 2 /64. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 168–173, 2001