Triangulated neighborhoods in even-hole-free graphs
Triangulated neighborhoods in even-hole-free graphs
复制标题
无偶孔图中的三角邻域
DOI：
10.1016/j.disc.2006.07.027
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Kristina Vuskovic
中科院分区：
文献类型：
--
作者：
M. D. Silva;Kristina Vuskovic
无偶洞图是不包含偶数长度的无弦圈作为导出子图的图。如果一个图不包含任何长度大于3的无弦圈，则称它为导出子图。我们证明了每一个偶无洞图都有一个邻域被三角化的节点。这意味着在一个无偶洞图中，有n个节点和m条边，最多有n+2m个最大团。它还产生了一个O（n2m）的算法，生成所有的最大团的偶孔免费图。事实上，这些结果得到了更大的一类图，其中包含偶孔免费图。
An even-hole-free graph is a graph that does not contain, as an induced subgraph, a chordless cycle of even length. A graph is triangulated if it does not contain any chordless cycle of length greater than three, as an induced subgraph. We prove that every even-hole-free graph has a node whose neighborhood is triangulated. This implies that in an even-hole-free graph, with n nodes and m edges, there are at most n+2m maximal cliques. It also yields an O(n2m) algorithm that generates all maximal cliques of an even-hole-free graph. In fact these results are obtained for a larger class of graphs that contains even-hole-free graphs.