DIMACS TR: 98-07

A Characterization for Parity Graphs and a Coloring Problem with Costs



Author: Klaus Jansen

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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-07.ps.gz

DIMACS Home Page