On the extension of bipartite to parity graphs
A path \(x_0x_1x_2\dots x_k\) of a graph \(G\) is induced if \(G\langle\{x_0,x_1,x_2,\dots, x_k\}\rangle\) has \(k\) edges. A graph \(G\) is a parity graph if, for every pair \((x,y)\) of vertices in \(G\), the lengths of induced \((x,y)\)-paths are of the same parity. Clearly, all bipartite graphs are parity graphs, so are distance-hereditary graphs. Using the split decomposition of Cunningham, the authors show that the recognition problem and the maximum weight clique problem for parity graphs can be solved in linear time.
scientific article; zbMATH DE number 1340635