beta-Perfect Graphs

beta-Perfect Graphs
复制标题

贝塔完美图

DOI：
--
复制
发表时间：
1996
期刊：
J. Comb. Theory B
影响因子：
--
通讯作者：
B. Reed
B. Reed
中科院分区：
--
文献类型：
--
作者：
S. Markossian;G. Gasparian;B. Reed

文献摘要

被引文献

相似文献

引入了s-完美图类。我们在这些图和完美图之间画出了许多相似之处。我们还引入了几类特殊的s-完美图。最后，我们证明了贪婪算法可以用至多2(？(G)？1)种颜色来给没有偶数无弦圈的图G着色。
The class ofs-perfect graphs is introduced. We draw a number of parallels between these graphs and perfect graphs. We also introduce some special classes ofs-perfect graphs. Finally, we show that the greedy algorithm can be used to colour a graphGwith no even chordless cycles using at most 2(?(G)?1) colours.