کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420433 | 683937 | 2010 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A forbidden subgraph characterization of line-polar bipartite graphs A forbidden subgraph characterization of line-polar bipartite graphs](/preview/png/420433.png)
A graph is polar if the vertex set can be partitioned into AA and BB in such a way that the subgraph induced by AA is a complete multipartite graph and the subgraph induced by BB 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].
Journal: Discrete Applied Mathematics - Volume 158, Issue 6, 28 March 2010, Pages 666–680