The recognition problem for line bigraphs (Q1398267)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The recognition problem for line bigraphs |
scientific article |
Statements
The recognition problem for line bigraphs (English)
0 references
29 July 2003
0 references
The line bigraph \(G=(E_1^\prime, E_2^\prime,F)\) of two graphs \(H_i=(V,E_i)\), \(i=1,2\), has disjoint copies \(E_i^\prime\) of \(E_i\) as partite sets, and \(\{e_1',e_2'\} \in F\) if \(e_1 \in E_1\) and \(e_2 \in E_2\) share an endpoint in \(V\). It is NP-complete to decide whether a given bipartite graph \(G\) is the line bigraph of suitable graphs \(H_1\) and \(H_2\). This problem becomes solvable in polynomial time if \(G\) is \(C_4\)-free or \(\delta(H_i) \geq 3\) for \(i=1,2\).
0 references
intersection bigraph
0 references
line bigraph
0 references
biclique
0 references
recognition
0 references
NP-completeness
0 references
polynomial-time algorithm
0 references