MPI-I-98-1-006
A new characterization for parity graphs and a coloring problem with costs
Jansen, Klaus
January 1998, 16 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-98-1-006.ps (163 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-006
BibTeX
@TECHREPORT{Jansen98-1-006,
AUTHOR = {Jansen, Klaus},
TITLE = {A new characterization for parity graphs and a coloring problem with costs},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-98-1-006},
MONTH = {January},
YEAR = {1998},
ISSN = {0946-011X},
}