2025/07/01 by Lili Hao, Hui Ma, Hao, Lili +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2507.00395
openalex publication_date 2025/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The toughness of a graph G is defined as the minimum value of |S|/c(G-S) over all cutsets S of G if G is noncomplete, and is defined to be ∞ if G is complete. For a real number t, we say that G is t-tough if its toughness is at least t. Followed from the classic 1956 result of Tutte, every more than (3)/(2)-tough planar graph on at least three vertices has a 2-factor. In 1999, Owens constructed a sequence of maximal planar graphs with toughness (3)/(2)-ε for any ε >0, but the graphs do not contain any 2-factor. He then posed the question of whether there exists a maximal planar graph with toughness exactly (3)/(2) and with no 2-factor. This question was recently answered affirmatively by the third author. This naturally leads to the question: under what conditions does a (3)/(2)-tough maximal planar graph contain a 2-factor? In this paper, we provide a sufficient condition for the existence of 2-factors in (3)/(2)-tough maximal planar graphs, stated as a bound on the distance between vertices of degree 3.