Displaying similar documents to “Algorithmic aspects of bipartite graphs.”

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

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

Existence of perfect matchings in a plane bipartite graph

Zhongyuan Che (2010)

Czechoslovak Mathematical Journal

Similarity:

We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the paper of F. Zhang, R. Chen and X. Guo (1985).

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

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