论文标题
产品图的薄度
Thinness of product graphs
论文作者
论文摘要
图的薄度是一个宽度参数，该参数概括了间隔图的某些属性，这正是薄的图。鉴于该图的合适表示，可以在多项式时间内解决许多NP完整问题。在本文中，我们研究了图形产品的薄度及其变化。我们表明，薄度通常对产品的表现“很好”，从某种意义上说，对于文献中定义的大多数图形产品，两个图的产物的薄度受其薄的功能（通常是乘积或总和）或其中一个的薄度以及另一个尺寸的薄界定。在某些情况下，我们还显示了这种功能的不存在。
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.
