Article ID Journal Published Year Pages File Type
4654887 European Journal of Combinatorics 2007 7 Pages PDF
Abstract

It was conjectured by Thomassen ([B. Alspach, C. Godsil, Cycle in graphs, Ann. Discrete Math. 27 (1985)], p. 466) that every longest circuit of a 3-connected graph must have a chord. This conjecture is verified for locally 4-connected planar graphs, that is, let NN be the set of natural numbers; then there is a function h:N→Nh:N→N such that, for every 4-connected graph GG embedded in a surface SS with Euler genus gg and face-width at least h(g)h(g), every longest circuit of GG has a chord.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,