Displaying similar documents to “The maximum number of perfect matchings in graphs with a given degree sequence.”

Choice-Perfect Graphs

Zsolt Tuza (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph G = (V,E) and a set Lv of admissible colors for each vertex v ∈ V (termed the list at v), a list coloring of G is a (proper) vertex coloring ϕ : V → S v2V Lv such that ϕ(v) ∈ Lv for all v ∈ V and ϕ(u) 6= ϕ(v) for all uv ∈ E. If such a ϕ exists, G is said to be list colorable. The choice number of G is the smallest natural number k for which G is list colorable whenever each list contains at least k colors. In this note we initiate the study of graphs in which the choice...

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

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.

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...

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...

Some Variations of Perfect Graphs

Magda Dettlaff, Magdalena Lemańska, Gabriel Semanišin, Rita Zuazua (2016)

Discussiones Mathematicae Graph Theory

Similarity:

We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure...

Distance perfectness of graphs

Andrzej Włoch (1999)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we propose a generalization of well known kinds of perfectness of graphs in terms of distances between vertices. We introduce generalizations of α-perfect, χ-perfect, strongly perfect graphs and we establish the relations between them. Moreover, we give sufficient conditions for graphs to be perfect in generalized sense. Other generalizations of perfectness are given in papers [3] and [7].

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...