The recognition problem for line bigraphs

作     者：Prisner, E 

作者机构：Univ Louisville Louisville KY 40292 USA 

出 版 物：《DISCRETE MATHEMATICS》 (离散数学)

年 卷 期：2003年第268卷第1-3期

页      面：243-256页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：intersection bigraph line bigraph NP-completeness polynomial-time algorithm 

摘      要：Given are two graphs H-1 = (V, E-1) and H-2 = (V, E-2) on the same vertex set. The line bigraph is the bipartite graph with the disjoint union of E-1 and E-2 as vertex set, and an edge between e(1) is an element of E-1 and e(2) is an element of E-2 if the edges have some common vertex in V. We first show that the problem to determine whether a given bipartite graph is the line bigraph of two such graphs is NP-complete. We then present two special cases where the question can be solved in polynomial time. A C-4-free bipartite graph is a line bigraph if and only if each component of the graph obtained by removing all degree-2 vertices has at most one cycle. Using the intersection multigraph of the set of all large bicliques, we then show that there is an efficient recognition algorithm for recognizing line bigraphs of two graphs both having minimum degree at least 3. (C) 2002 Elsevier Science B.V. All rights reserved.