Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F. Partitioning chordal graphs into independent sets and cliques. (Portuguese. English summary) Zbl 1208.05111 TEMA, Tend. Mat. Apl. Comput. 3, No. 1, 147-155 (2002). 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. Cited in 1 Document 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 \textit{P. Hell} et al., TEMA, Tend. Mat. Apl. Comput. 3, No. 1, 147--155 (2002; Zbl 1208.05111) Full Text: DOI