×

On generalized split graphs. (English) Zbl 0981.05076

Szwarcfiter, Jayme (ed.), Proceedings of the Brazilian symposium on graphs, algorithms and combinatorics, Fortaleza, Ceará, Brazil, March 17-19, 2001. Extended abstracts. Amsterdam: Elsevier, Electron. Notes Discrete Math. 7, no pag., electronic only (2001).
Summary: We prove that in a chordal graph the maximum number of independent (i.e., disjoint and nonadjacent) \(K_r\)’s equals the minumum number of cliques that meet all \(K_r\)’s. When \(r=1\), this implies that chordal graphs are perfect. When \(r=2\), it contains a well-known forbidden subgraph characterization of split graphs. We also discuss algorithms for both these problems. In particular, we illustrate the techniques by giving a new simple recognition algorithm for split graphs. We apply these results to the following generalization of split graphs: A graph is said to be a \((k,l)\)-graph if its vertex set can be partitioned into \(k\) independent sets and \(l\) cliques. Much of the appeal of split graphs is due to the fact that they are chordal, a property not shared by \((k,l)\)-graphs in general. (For instance, being a \((k,0)\)-graph is equivalent to being \(k\)-colourable.) However, if we keep the assumption of chordality, nice algorithms and characterization theorems are possible. Indeed, our result gives a forbidden subgraph characterization of (and a polynomial time recognition algorithm for) chordal \((k,l)\)-graphs.
For the entire collection see [Zbl 0968.00006].

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite