b'@techreport{Jansen98-1-006,'b'\nTITLE = {A new characterization for parity graphs and a coloring problem with costs},\nAUTHOR = {Jansen, Klaus},\nLANGUAGE = {eng},\nNUMBER = {MPI-I-1998-1-006},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1998},\nDATE = {1998},\nABSTRACT = {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.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'