Linear Time Recognition of Bipartite Star123-Free Graphs
Ruzayn Quaddoura
Faculty of Science and Information Technology, Zarqa Private University, Jordan
Abstract: In this paper, we present a linear time recognition algorithm for recognizing bipartite graphs without induced subgraphs isomorph to star123. Bipartite star123-free graphs are a natural generalization of both weak bisplit and Star123, Sun4-free bipartite graphs, both further generalizing bicographs.
Keywords: Bipartite graph, decomposition of graphs, complexity.
Received October 17, 2004; accepted July 25, 2005