Premium
Nearly light cycles in embedded graphs and crossing‐critical graphs
Author(s) -
Lomelí Mario,
Salazar Gelasio
Publication year - 2006
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/jgt.20172
Subject(s) - combinatorics , mathematics , crossing number (knot theory) , vertex (graph theory) , graph , bounded function , 1 planar graph , discrete mathematics , line graph , mathematical analysis , intersection (aeronautics) , engineering , aerospace engineering
We find a lower bound for the proportion of face boundaries of an embedded graph that are nearly light (that is, they have bounded length and at most one vertex of large degree). As an application, we show that every sufficiently large k ‐crossing‐critical graph has crossing number at most 2 k + 23. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 151–156, 2006