de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

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

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44695

Jansen,  Klaus
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

1998-1-006
(beliebiger Volltext), 10KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

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.

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.