Pathwidth of cubic graphs and exact algorithms

We prove that for any ɛ>0 there exists an integer nɛ such that the pathwidth of every cubic (or 3-regular) graph on n>nɛ vertices is at most (1/6+ɛ)n. Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three.