On the extension of bipartite to parity graphs
type: Item
instance of: scholarly article
title: On the extension of bipartite to parity graphs
zbMATH Open document ID: 0933.05132
DOI: 10.1016/S0166-218X(99)00074-8
author: Serafino Cicerone
author: Gabriele Di Stefano
published in: Discrete Applied Mathematics
publication date: 2000-04-04T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1340635
zbMATH Keywords: parity graph
zbMATH Keywords: bipartite graphs
zbMATH Keywords: distance-hereditary graphs
zbMATH Keywords: split decomposition
reviewed by: G. Gutin
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1340635