Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646676 | Discrete Mathematics | 2016 | 10 Pages |
In this paper we study unavoidable sets of types of 3-paths for families of planar graphs with minimum degree at least 2 and a given girth gg. A 3-path of type (i,j,k)(i,j,k) is a path uvwuvw on three vertices uu, vv, and ww such that the degree of uu (resp. vv, resp. ww) is at most ii (resp. jj, resp. kk). The elements i,j,ki,j,k are called parameters of the type. The set SS of types of paths is unavoidable for a family FF of graphs if each graph GG from FF contains a path of the type from SS. An unavoidable set SS of types of paths is optimal for the family FF if neither any type can be omitted from SS, nor any parameter of any type from SS can be decreased.We prove that the set SgSg (resp. S′gS′g) is an optimal set of types of 3-paths for the family of plane graphs having δ(G)≥2δ(G)≥2 and girth g(G)≥gg(G)≥g where (i)S5={(2,∞,2),(2,3,5),(2,4,3),(3,3,3)}S5={(2,∞,2),(2,3,5),(2,4,3),(3,3,3)},(ii)S7={(2,3,3),(2,5,2)}S7={(2,3,3),(2,5,2)},S7′={(2,2,6),(2,3,3),(2,4,2)},(iii)S8={(2,2,5),(2,3,2)}S8={(2,2,5),(2,3,2)},(iv)S10={(2,4,2)}S10={(2,4,2)},S10′={(2,2,3),(2,3,2)},(v)S11={(2,2,3)}S11={(2,2,3)}.