Berge trigraphs
Berge trigraphs
复制标题
贝尔格三字母组
DOI：
--
复制
发表时间：
2006
影响因子：
0.9
通讯作者：
M. Chudnovsky
中科院分区：
文献类型：
--
作者：
M. Chudnovsky
一个图是Berge图，如果它的导出子图都不是长度至少为5或1的补数的奇圈。在与Robertson、Seymour和托马斯的合作中，我们最近证明了关于Berge图的色数的一个猜想--强完美图定理。证明包括表明，每一个贝尔格图要么属于一个少数几个基本类，或承认之一的几种分解。我们使用了三种分解：斜分拆，2-连接和适当的齐次对。当时，我们不确定这三种分解是否都是必要的。在这篇文章中，我们证明了适当的齐次对分解实际上是不必要的。这是“贝尔格三图”一般分解定理的结果。
A graph is Berge if no induced subgraph of it is an odd cycle of length at least five or the complement of one. In joint work with Robertson, Seymour, and Thomas we recently proved the Strong Perfect Graph Theorem, which was a conjecture about the chromatic number of Berge graphs. The proof consisted of showing that every Berge graph either belongs to one of a few basic classes, or admits one of a few kinds of decompositions. We used three kinds of decompositions: skew‐partitions, 2‐joins, and proper homogeneous pairs. At that time we were not sure whether all three decompositions were necessary. In this article we show that the proper homogeneous pair decomposition is in fact unnecessary. This is a consequence of a general decomposition theorem for “Berge trigraphs.”