max planck institut
informatik
informatik
MPI-I-98-1-006. January 1998, 16 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry
Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:
| To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |
|---|---|
| 163 KBytes | |
| Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView | |
BibTeX