# Item

ITEM ACTIONSEXPORT

Released

Report

#### A new characterization for parity graphs and a coloring problem with costs

##### Fulltext (public)

MPI-I-98-1-006.pdf

(Any fulltext), 199KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Jansen, K.(1998). *A new characterization for parity graphs
and a coloring problem with costs* (MPI-I-1998-1-006). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-7BE2-3

##### Abstract

In this paper, we give a characterization for parity graphs.
A graph is a parity graph, if and only if 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 \times K_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 problem with costs. For the case that the costs $k_{v,3} = k_{v,c}$
for each color $c \ge 3$ and vertex $v \in V$, we show that the
polyhedron contains only
integral $0 / 1$ extrema if and only if the graph $G$ is a parity graph.