Trees with proper thinness 2
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915289998819328 |
|---|---|
| author | Bonomo-Braberman, Flavia Maqueda, Ignacio Pardal, Nina |
| author_facet | Bonomo-Braberman, Flavia Maqueda, Ignacio Pardal, Nina |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11382 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Trees with proper thinness 2 Bonomo-Braberman, Flavia Maqueda, Ignacio Pardal, Nina Combinatorics Discrete Mathematics 05C75 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. |
| title | Trees with proper thinness 2 |
| topic | Combinatorics Discrete Mathematics 05C75 |
| url | https://arxiv.org/abs/2505.11382 |