A forbidden subgraph characterization of line-polar bipartite graphs

作者：Huang, Jing^*; Xu, Baogang

来源：Discrete Applied Mathematics, 2010, 158(6): 666-680.

DOI：10.1016/j.dam.2009.12.012

• Polar graph
• Line-polar graph
• Line-monopolar graph
• Forbidden subgraph characterization

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,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].

• 出版日期2010-3-28
• 单位南京师范大学