On the extension of bipartite to parity graphs (Q1302156): Difference between revisions

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.