Optimal unavoidable sets of types of 3-paths for planar graphs of given girth

• Published in: Discrete mathematics 2016-02, Vol.339 (2), p.780-789
• Main Authors: Jendrol’, S., Maceková, M., Montassier, M., Soták, R.
• Format: Article
• Language: English
• Subjects: 3-path; Computer Science; Discrete Mathematics; Girth; Optimal unavoidable set; Planar graph
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2015.10.016

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 g. A 3-path of type (i,j,k) is a path uvw on three vertices u, v, and w such that the degree of u (resp. v, resp. w) is at most i (resp. j, resp. k). The elements i,j,k are called parameters of the type. The set S of types of paths is unavoidable for a family F of graphs if each graph G from F contains a path of the type from S. An unavoidable set S of types of paths is optimal for the family F if neither any type can be omitted from S, nor any parameter of any type from S can be decreased. We prove that the set Sg (resp. S′g) is an optimal set of types of 3-paths for the family of plane graphs having δ(G)≥2 and girth g(G)≥g where (i)S5={(2,∞,2),(2,3,5),(2,4,3),(3,3,3)},(ii)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)},(iv)S10={(2,4,2)},S10′={(2,2,3),(2,3,2)},(v)S11={(2,2,3)}.