Displaying similar documents to “Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases”

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

Forbidden Structures for Planar Perfect Consecutively Colourable Graphs

Marta Borowiecka-Olszewska, Ewa Drgas-Burchardt (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose...

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

Several results on chordal bipartite graphs

Mihály Bakonyi, Aaron Bono (1997)

Czechoslovak Mathematical Journal

Similarity:

The question of generalizing results involving chordal graphs to similar concepts for chordal bipartite graphs is addressed. First, it is found that the removal of a bisimplicial edge from a chordal bipartite graph produces a chordal bipartite graph. As consequence, occurance of arithmetic zeros will not terminate perfect Gaussian elimination on sparse matrices having associated a chordal bipartite graph. Next, a property concerning minimal edge separators is presented. Finally, it is...