Header menu link for other important links
One-three join: A graph operation and its consequences
M.A. Shalu,
Published in University of Zielona Gora
Volume: 37
Issue: 3
Pages: 633 - 647
In this paper, we introduce a graph operation, namely one-three join. We show that the graph G admits a one-three join if and only if either G is one of the basic graphs (bipartite, complement of bipartite, split graph) or G admits a constrained homogeneous set or a bipartite-join or a join. Next, we define MH as the class of all graphs generated from the induced subgraphs of an odd hole-free graph H that contains an odd anti-hole as an induced subgraph by using one-three join and co-join recursively and show that the maximum independent set problem, the maximum clique problem, the minimum coloring problem, and the minimum clique cover problem can be solved efficiently for MH.
About the journal
JournalDiscussiones Mathematicae - Graph Theory
PublisherUniversity of Zielona Gora