In [1], the following result is proved:
Theorem: Let k be a positive integer and let G be a 3-connected infinite planar graph of subexponential growth. Then G contains infinitely many disjoint k-paths whose vertices have degree at most 6k.
There are planar graphs of polynomial growth in which for every infinite path, the average degree of its first k initial vertices is of order log k. Examples of such graphs are not trivial, and it seems that things cannot get much worse than that.
Conjecture ([1]): There is a constant C such that every 3-connected infinite planar graph of subexponential growth contains a one-way-infinite path P = v1v2v3... such that for every positive integer k, deg(v1) + deg(v2) + ... + deg(vk) < C k log k.
A proof of this conjecture would solve an open problem about finite graphs [2, Problem 3].
[1] B. Mohar, Light structures in infinite planar graphs without the strong isoperimetric property, Trans. Amer. Math. Soc. 354 (2002) 3059-3074.
[2] I. Fabrici, S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Comb. 13 (1997) 245-250.
Send comments to Bojan.Mohar@uni-lj.si