×

Partitioning chordal graphs into independent sets and cliques. (Portuguese. English summary) Zbl 1208.05111

Summary: We consider the following generalization of split graphs: A graph \(G\) is a \((k,l)\)-graph if its set of vertices can be partitioned into \(k\) independent sets and \(l\) cliques (a clique is a not necessarily maximal complete subgraph). Therefore, \((k,l)\)-graphs are a generalization of split graphs, which correspond to \((1,1)\)-graphs. Split graphs can be recognized efficiently [S. Földes and P. L. Hammer, in: Proc. 8th southeast. Conf. on Combinatorics, graph theory, and computing; Baton Rouge 1977, 311–315 (1977; Zbl 0407.05071)]. Furthermore, the classical problems of combinatorial optimization are also solved efficiently in this class. In fact, our main result is a characterization of \((k,l)\)-chordal graphs. We also present an algorithm for recognizing \((k,l)\)-chordal graphs whose complexity is \(O(n(m+n))\). When \(k=l=1\), our algorithm has complexity \(O(m+n)\).
In particular, we obtain a simpler and more efficient algorithm for recognizing split graphs, from which it becomes easy to derive the known characterization of split graphs by forbidden subgraphs.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 0407.05071
PDFBibTeX XMLCite
Full Text: DOI