The thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable representation of the graph. In this paper we study the thinness and its variations of graph products. We show that the thinness behaves "well" in general for products, in the sense that for most of the graph products defined in the literature, the thinness of the product of two graphs is bounded by a function (typically product or sum) of their thinness, or of the thinness of one of them and the size of the other. We also show for some cases the non-existence of such a function.
翻译：图表的薄度是一个宽度参数,它概括了间距图的某些属性, 这正是薄度图一的图形。 许多NP的完整问题可以在多角时间解决, 对于有细度的图形来说, 以适当的图形表示。 在本文中, 我们研究图产品的薄度及其变异性。 我们显示, 对于产品来说, 薄度一般是“ 良好” 的, 也就是说, 对于文献中定义的大多数图形产品来说, 两个图形的产物的薄度是被其薄度的函数( 典型产品或总和) 所捆绑的, 或者其中之一的薄度和另一个的大小。 我们有时还显示, 不存在这样的函数 。
相关内容
微信扫码咨询专知VIP会员