Trees with proper thinness 2
Flavia Bonomo-Braberman and Ignacio Maqueda and Nina Pardal
图形的正确薄度是一个不变的,它概括了适当的间隔图的概念。 每个图形都有适当的薄度的数值,具有适当薄度的图形1正是适当的间隔图。 图形是适当的k-薄,如果它的顶点可以排序,这样顶点有一个分区的顶点到k类满足,对于每个三重顶点r < s < t,这样r和t之间有一个边缘,这是真的,如果r和s属于同一个类,那么s和t之间有一个边缘,如果s和t属于同一个类,那么有一个边缘。 适当的薄度是k的最小值,因此图形是适当的k-薄。 在这项工作中,我们专注于计算树木的适当薄度。 我们表征了适当的薄度2,无论是结构上还是通过其最小的禁止诱导子图。 获得的表征导致了多项式时间识别算法。 我们还展示了为什么为适当薄的树木2获得的结构结果不能直接推广到适当的薄度3的树木。
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 th...