Graphoidal bipartite graphs (Q1343223)

For many years a characterization of those graphs \(G\) so that \(G\cong L(H)\), where \(L(H)\) is the line graph of the graph \(H\), has been known. The authors generalize this notion as follows. A graphoidal cover \(\psi_ G\) of \(G\) is a partition of \(E(G)\) into paths so that each vertex is the interior vertex of at most one path. The intersection graph \(\Omega(\psi_ G)\) of \(\psi_ G\) has as vertices the paths in \(\psi_ G\) and two vertices are adjacent if the corresponding paths intersect. Clearly if \(\psi_ G\) is the set of all edges in \(G\), then \(\Omega(\psi_ G)\cong L(G)\). A graph \(G\) is graphoidal if there is a graph \(H\) and graphoidal cover \(\psi_ H\) so that \(G\cong \Omega(\psi_ H)\). The problem is to characterize graphoidal graphs. The authors show: (1) all trees are graphoidal; (2) the subdivision graph of any graph is graphoidal; (3) a bipartite graph is graphoidal if and only if it does not contain an edge- induced subgraph \(H\) of minimum degree 3 satisfying \(| E(H)|= 2| V(H)|+ 1\).