The parity graph is a graph in which any two generated paths between two vertices have the same parity - either both paths have odd lengths, or both paths have even lengths [1] . This class of graphs was the first to be studied and given the name Barlet and Uri [2] .
Content
Related Graph Classes
Parity graphs include distance-inherited graphs in which any two generated paths between two vertices have the same lengths. They also include bipartite graphs , which can be described similarly as graphs in which any two paths (not necessarily generated) between two vertices have the same parity, and edge-perfect graphs generalizing bipartite graphs. Any parity graph is a Meinel graph , that is, a graph in which any cycle of odd length (length 5 or more) has at least two chords. In the parity graph, any long cycle can be divided into two paths of different parity, none of which is a separate edge and at least one chord is necessary so that these paths are not generated paths. Then, after breaking the cycle into two paths between the end points of the first chord, a second chord is necessary so that the second path is not generated. Since Meinel graphs are perfect graphs , parity graphs are also perfect [1] . These are exactly graphs whose direct product with a separate edge remains a perfect graph [3] .
Algorithms
A graph is a parity graph if and only if any component of its is either a complete graph or a bipartite graph . Based on this description, you can check whether the graph is a parity graph for linear time . The same description leads to a generalization of some optimization algorithms on graphs from bipartite graphs to parity graphs. For example, using graph splitting, one can find the weighted largest independent set of the parity graph in polynomial time [4] .
Notes
- ↑ 1 2 Parity graphs , Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
- ↑ Burlet, Uhry, 1984 , p. 253-277.
- ↑ Jansen, 1998 , p. 249-260.
- ↑ Cicerone, Di Stefano, 1997 , p. 354–363.
Literature
- Burlet M., Uhry J.-P. Parity graphs // Topics on perfect graphs. - Amsterdam: North-Holland, 1984. - T. 88. - (North-Holland Math. Stud.). - DOI : 10.1016 / S0304-0208 (08) 72939-6 .
- Klaus Jansen. A new characterization for parity graphs and a coloring problem with costs // LATIN'98: theoretical informatics (Campinas, 1998). - Springer, Berlin, 1998 .-- T. 1380. - (Lecture Notes in Comput. Sci.). - DOI : 10.1007 / BFb0054326 .
- Serafino Cicerone, Gabriele Di Stefano. On the equivalence in complexity among basic problems on bipartite and parity graphs // Algorithms and computation (Singapore, 1997). - Springer, Berlin, 1997. - T. 1350. - (Lecture Notes in Comput. Sci.). - DOI : 10.1007 / 3-540-63890-3_38 .