Displaying similar documents to “Choice-Perfect Graphs”

A note on pm-compact bipartite graphs

Jinfeng Liu, Xiumei Wang (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is called perfect matching compact (briefly, PM-compact), if its perfect matching graph is complete. Matching-covered PM-compact bipartite graphs have been characterized. In this paper, we show that any PM-compact bipartite graph G with δ (G) ≥ 2 has an ear decomposition such that each graph in the decomposition sequence is also PM-compact, which implies that G is matching-covered

The perfection and recognition of bull-reducible Berge graphs

Hazel Everett, Celina M. H. de Figueiredo, Sulamita Klein, Bruce Reed (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x , a , b , c , d and five edges x a , x b , a b , a d , b c . A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows...

A note on the hardness results for the labeled perfect matching problems in bipartite graphs

Jérôme Monnot (2008)

RAIRO - Operations Research

Similarity:

In this note, we strengthen the inapproximation bound of (log) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, (2005) 81–88, using a self improving operation in some hard instances. It is interesting to note that this self improving operation does not work for all instances. Moreover, based on this approach we deduce that the problem does not admit constant approximation algorithms for connected planar...