## Light Infinite Paths in Planar Graphs With Subexponential Growth

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 6*k*.

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 = v_{1}v_{2}v_{3}...
such that for every positive integer *k*, deg(v_{1}) + deg(v_{2})
+ ... + deg(v_{k}) < *C k* log *k*.

A proof of this conjecture would solve an open problem about finite graphs
[2, Problem 3].

References:
[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

##### Revised: junij 13, 2002.