Convex-Round and Concave-Round Graphs
Convex-Round and Concave-Round Graphs
复制标题
凸圆图和凹圆图
DOI：
--
复制
发表时间：
2000
影响因子：
0.8
通讯作者：
Anders Yeo
中科院分区：
文献类型：
--
作者：
J. Bang;Jing Huang;Anders Yeo
我们引入两类新的图，分别称为凸圆图和凹圆图。凸圆（凹圆）图是那些顶点可以循环枚举的图，使得每个顶点的（闭）邻域在枚举中形成一个区间。因此，这两个类通过补集相互转化。我们证明这两类图都具有良好的结构特性。我们观察到凹圆图类正确地包含真圆弧图类，并且根据 Tucker [ Pacific J. Math., 39 (1971), pp. 535--545] 的结果，正确地包含在一般圆弧图类中。我们指出凸圆图和凹圆图可以在 O(n+m) 时间内识别（这里 n 表示顶点的数量，m 表示所讨论的图的边的数量）。我们证明，凸圆（凹圆）图的色数可以在 O(n+m) (O(n2)) 时间内找到。我们描述了用于寻找凸圆图类的最大团、最大匹配和哈密顿循环（如果存在）的最佳 O(n+m) 时间算法。最后，我们提出了一些关于两个新类和相关的第三类图的结构和算法属性的开放问题和猜想。
We introduce two new classes of graphs which we call convex-round, respectively concave-round graphs. Convex-round (concave-round) graphs are those graphs whose vertices can be circularly enumerated so that the (closed) neighborhood of each vertex forms an interval in the enumeration. Hence the two classes transform into each other by taking complements. We show that both classes of graphs have nice structural properties. We observe that the class of concave-round graphs properly contains the class of proper circular arc graphs and, by a result of Tucker [ Pacific J. Math., 39 (1971), pp. 535--545], is properly contained in the class of general circular arc graphs. We point out that convex-round and concave-round graphs can be recognized in O(n+m) time (here n denotes the number of vertices and m the number of edges of the graph in question). We show that the chromatic number of a graph which is convex-round (concave-round) can be found in time O(n+m) (O(n2)). We describe optimal O(n+m) time algorithms for finding a maximum clique, a maximum matching, and a Hamiltonian cycle (if one exists) for the class of convex-round graphs. Finally, we pose a number of open problems and conjectures concerning the structure and algorithmic properties of the two new classes and a related third class of graphs.