In this paper, we give a characterization for parity graphs. A graph is a parity graph, if and only fi for every pair of vertices all minimal chains joining them have the same parity. We prove that G is a parity graph, if and only if the Cartesian product G*K sub 2 is a perfect graph. Furthermore, as a consequence we get a result for the polyhedron corresponding to an integer linear program formulation of a coloring prolem with costs. For the case that the costs k sub v,3=k sub v,c for each color c >3 and vertex v V, we show that the polyhedron contains only integral 0/1 extrema if and only if the graph G is a parity graph.
展开▼
机译：在本文中，我们给出了奇偶图的特征。一个图是一个奇偶校验图，如果且仅对于每对顶点的fi，连接它们的所有最小链具有相同的奇偶校验。当且仅当笛卡尔积G * K sub 2是理想图时，我们证明G是奇偶图。此外，结果，我们得到了多面体的结果，该多面体对应于带有成本的着色问题的整数线性程序公式。对于每种颜色c> 3和顶点v V的成本k sub v，3 = k sub v，c的情况，我们证明，当且仅当图G为奇偶校验时，多面体仅包含整数0/1极值。图形。
展开▼
