2025/05/16 by Flavia Bonomo, Bonomo-Braberman, Flavia, Ignacio Maqueda +3
Computer Science · #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2505.11382
openalex publication_date 2025/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The proper thinness of a graph is an invariant that generalizes the concept of a proper interval graph. Every graph has a numerical value of proper thinness and the graphs with proper thinness~1 are exactly the proper interval graphs. A graph is proper k-thin if its vertices can be ordered in such a way that there is a partition of the vertices into k classes satisfying that for each triple of vertices r < s < t, such that there is an edge between r and t, it is true that if r and s belong to the same class, then there is an edge between s and t, and if s and t belong to the same class, then there is an edge between r and s. The proper thinness is the smallest value of k such that the graph is proper k-thin. In this work we focus on the calculation of proper thinness for trees. We characterize trees of proper thinness~2, both structurally and by their minimal forbidden induced subgraphs. The characterizations obtained lead to a polynomial-time recognition algorithm. We furthermore show why the structural results obtained for trees of proper thinness~2 cannot be straightforwardly generalized to trees of proper thinness~3.