The recognition problem for line bigraphs Export

@article{prisner03, abstract = {Given are two graphs H1=(V,E1) and H2=(V,E2) on the same vertex set. The line bigraph is the bipartite graph with the disjoint union of E1 and E2 as vertex set, and an edge between e1[set membership, variant]E1 and e2[set membership, variant]E2 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 C4-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.}, author = {Prisner, Erich}, citeulike-article-id = {2648324}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0012-365X(02)00691-X}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6V00-47HKD8V-17/2/10a8e38c95d9c17d057f3640237b03c4}, day = {6}, doi = {10.1016/S0012-365X(02)00691-X}, journal = {Discrete Mathematics}, keywords = {algorithms, graphs, mathematics}, month = {July}, number = {1-3}, pages = {243--256}, posted-at = {2008-04-10 09:14:02}, priority = {2}, title = {The recognition problem for line bigraphs}, url = {http://dx.doi.org/10.1016/S0012-365X(02)00691-X}, volume = {268}, year = {2003} }

TY - JOUR ID - prisner03 L3 - citeulike-article-id:2648324 N2 - Given are two graphs H1=(V,E1) and H2=(V,E2) on the same vertex set. The line bigraph is the bipartite graph with the disjoint union of E1 and E2 as vertex set, and an edge between e1[set membership, variant]E1 and e2[set membership, variant]E2 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 C4-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. IS - 1-3 JF - Discrete Mathematics EP - 256 TI - The recognition problem for line bigraphs VL - 268 SP - 243 KW - algorithms KW - graphs KW - mathematics AU - Prisner, Erich PY - 2003/07/06/ UR - http://dx.doi.org/10.1016/S0012-365X(02)00691-X ER -