ON 2-CONNECTED SPANNING SUBGRAPHS WITH LOW MAXIMUM DEGREE

Given a graph G, let a k-trestle of G be a 2-connected spanning subgra ph of G of maximum degree at most k. Also, let chi(G) be the Euler cha racteristic of G. This paper shows that every 3-connected graph G has a (10-2 chi(G))-trestle. If chi(G)less than or equal to -5, this is im proved to 8-2 chi(G), and for chi(G)less than or equal to -10, this is further improved to 6-2 chi(G). This result is shown to be best possi ble for almost all values of chi(G) by the demonstration of 3-connecte d graphs embedded on each surface of Euler characteristic chi less tha n or equal to 0 which have no (5-2 chi)-trestle. Also, it is shown tha t a 4-connected graph embeddable on a surface with non-negative Euler characteristic has a 3-trestle, approaching a conjecture of Nash-Willi ams. (C) 1998 Academic Press.