Displaying similar documents to “A note on the hardness results for the labeled perfect matching problems in bipartite graphs”

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.

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