A forbidden subgraph characterization of line-polar bipartite graphs |
| |
Authors: | Jing Huang Baogang Xu |
| |
Affiliation: | a Department of Mathematics and Statistics, University of Victoria, P.O. Box 3060 STN CSC, Victoria, B.C., Canada, V8W 3R4 b School of Mathematics and Computer Science, Nanjing Normal University, Nanjing, PR China |
| |
Abstract: | A graph is polar if the vertex set can be partitioned into A and B in such a way that the subgraph induced by A is a complete multipartite graph and the subgraph induced by B is a disjoint union of cliques. Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. However, recognizing polar graphs is an NP-complete problem in general. This led to the study of the polarity of special classes of graphs such as cographs and chordal graphs, cf. Ekim et al. (2008) [7] and [5]. In this paper, we study the polarity of line graphs and call a graph line-polar if its line graph is polar. We characterize line-polar bipartite graphs in terms of forbidden subgraphs. This answers a question raised in the fist reference mentioned above. Our characterization has already been used to develop a linear time algorithm for recognizing line-polar bipartite graphs, cf. Ekim (submitted for publication) [6]. |
| |
Keywords: | Polar graph Line-polar graph Line-monopolar graph Forbidden subgraph characterization |
本文献已被 ScienceDirect 等数据库收录! |
|