Maximum independent sets in (pyramid, even hole)-free graphs
Maximum independent sets in (pyramid, even hole)-free graphs
复制标题
无（金字塔、偶孔）图中的最大独立集
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Kristina Vuskovic
中科院分区：
文献类型：
--
作者：
M. Chudnovsky;Stéphan Thomassé;Nicolas Trotignon;Kristina Vuskovic
图中的emph{hole}是一个至少有4个顶点的诱导环。如果一个图在偶数个顶点上不包含一个洞，那么它就是emph{even-hole-free}。emph{金字塔}是由三条无弦路径组成的图$P_1 = A点b_1$，
A emph{hole} in a graph is an induced cycle with at least 4 vertices. A graph is emph{even-hole-free} if it does not contain a hole on an even number of vertices. A emph{pyramid} is a graph made of three chordless paths $P_1 = a dots b_1$,
$P_2 = a dots b_2$, $P_3 = a dots b_3$ of length at least~1, two of which have length at least 2, vertex-disjoint except at $a$, and such that $b_1b_2b_3$ is a triangle and no edges exist between the paths except those of the triangle and the three edges incident with $a$.
We give a polynomial time algorithm to compute a maximum weighted independent set in a even-hole-free graph that contains no pyramid as an induced subgraph. Our result is based on a decomposition theorem and on bounding the number of minimal separators. All our results hold for a slightly larger class of graphs, the class of (square, prism, pyramid, theta, even wheel)-free graphs.
关于偶无洞图的秩宽度
DOI：
10.48550/arxiv.1611.09907
发表时间：
2016
期刊：
arXiv e-prints
影响因子：
--
作者：
Adler Isolde
通讯作者：
Adler Isolde