Displaying similar documents to “The perfection and recognition of bull-reducible Berge graphs”

Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases

E. Bampis, A. Giannakos, A. Karzanov, Y. Manoussakis, I. Milis (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

It is known that finding a perfect matching in a general graph is -equivalent to finding a perfect matching in a 3-regular ( cubic) graph. In this paper we extend this result to both, planar and bipartite cases. In particular we prove that the construction problem for perfect matchings in planar graphs is as difficult as in the case of planar cubic graphs like it is known to be the case for the famous Map Four-Coloring problem. Moreover we prove that the existence...

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

Comparing Imperfection Ratio and Imperfection Index for Graph Classes

Arie M.C.A. Koster, Annegret K. Wagler (2009)

RAIRO - Operations Research

Similarity:

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs where the stable set polytope STAB() coincides with the fractional stable set polytope QSTAB(). For all imperfect graphs it holds that STAB() ⊂ QSTAB(). It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph...

Comparing imperfection ratio and imperfection index for graph classes

Arie M. C. A. Koster, Annegret K. Wagler (2008)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB ( G ) coincides with the fractional stable set polytope QSTAB ( G ) . For all imperfect graphs G it holds that STAB ( G ) ⊂ QSTAB ( G ) . It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss...

On a perfect problem

Igor E. Zverovich (2006)

Discussiones Mathematicae Graph Theory

Similarity:

We solve Open Problem (xvi) from Perfect Problems of Chvátal [1] available at ftp://dimacs.rutgers.edu/pub/perfect/problems.tex: Is there a class C of perfect graphs such that (a) C does not include all perfect graphs and (b) every perfect graph contains a vertex whose neighbors induce a subgraph that belongs to C? A class P is called locally reducible if there exists a proper subclass C of P such that every graph in P contains a local subgraph...

Mycielskians and matchings

Tomislav Doslić (2005)

Discussiones Mathematicae Graph Theory

Similarity:

It is shown in this note that some matching-related properties of graphs, such as their factor-criticality, regularizability and the existence of perfect 2-matchings, are preserved when iterating Mycielski's construction.

Conditions for β-perfectness

Judith Keijsper, Meike Tewes (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A β-perfect graph is a simple graph G such that χ(G') = β(G') for every induced subgraph G' of G, where χ(G') is the chromatic number of G', and β(G') is defined as the maximum over all induced subgraphs H of G' of the minimum vertex degree in H plus 1 (i.e., δ(H)+1). The vertices of a β-perfect graph G can be coloured with χ(G) colours in polynomial time (greedily). The main purpose of this paper is to give necessary and sufficient conditions, in terms of forbidden...