×

Partitioning chordal graphs into independent sets and cliques. (English) Zbl 1043.05097

Summary: We consider the following generalization of split graphs: A graph is said to be a (\(k,\ell\))-graph if its vertex set can be partitioned into \(k\) independent sets and \(\ell\) cliques. (Split graphs are obtained by setting \(k=\ell=1\).) Much of the appeal of split graphs is due to the fact that they are chordal, a property not shared by (\(k,\ell\))-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 main result is a forbidden subgraph characterization of chordal (\(k,\ell\))-graphs. We also give an O(\(n(m+n)\)) recognition algorithm for chordal (\(k,\ell\))-graphs. When \(k=1\), our algorithm runs in time O(\(m+n\)).
In particular, we obtain a new simple and efficient greedy algorithm for the recognition of split graphs, from which it is easy to derive the well-known forbidden subgraph characterization of split graphs. The algorithm and the characterization extend, in a natural way, to the ‘list’ (or ‘pre-colouring extension’) version of the split partition problem – given a graph with some vertices pre-assigned to the independent set, or to the clique, is there a split partition extending this pre-assignment? Another way to think of our main result is the following min–max property of chordal graphs: for each integer \(r \geqslant 1\), the maximum number of independent \(K_r\)’s (i.e., of vertex disjoint subgraphs of \(G\), each isomorphic to \(K_r\), with no edges joining two of the subgraphs) equals the minimum number of cliques of \(G\) that meet all the \(K_r\)’s of \(G\).

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)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M. O.; Moore, E. H., Extending graph colorings, J. Combin. Theory B, 77, 83-95 (1999) · Zbl 1024.05027
[2] Brandstädt, A., Partitions of graphs into one or two independent sets and cliques, Discrete Math., 152, 47-54 (1996) · Zbl 0853.68140
[3] Brandstädt, A., Corrigendum: Partitions of graphs into one or two independent sets and cliques, Discrete Math., 186, 295-295 (1998)
[4] Brandstädt, A.; Le, V. B.; Szymczak, T., The complexity of some problems related to graph 3-colorability, Discrete Appl. Math., 89, 59-73 (1998) · Zbl 0927.68063
[5] Dragan, F. F.; Brandstädt, A., \(r\)-dominating cliques in graphs with hypertree structure, Discrete Math., 162, 93-108 (1996) · Zbl 0870.05038
[6] Feder, T.; Hell, P.; Klein, S.; Motwani, R., Complexity of graph partition problems, (Thatcher, F. W.; Miller, R. E., Proceedings of the 31st Annual ACM Symposium on Theory of Computing-STOC’99 (1999), Plenum Press: Plenum Press New York), 464-472 · Zbl 1345.68171
[7] Foldes, S.; Hammer, P., Split graphs, Congr. Numer., 19, 311-315 (1977)
[8] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[9] P. Hell, S. Klein, L.T. Nogueira, F. Protti, On generalized split graphs, GRACO’2001, Electronic Notes in Discrete Mathematics, Vol. 7, Elsevier, Amsterdam, 2001.; P. Hell, S. Klein, L.T. Nogueira, F. Protti, On generalized split graphs, GRACO’2001, Electronic Notes in Discrete Mathematics, Vol. 7, Elsevier, Amsterdam, 2001. · Zbl 0981.05076
[10] Kratochvíl, J.; Sebö, A., Coloring precolored perfect graphs, J. Graph Theory, 25, 207-215 (1997) · Zbl 0876.05035
[11] L.T. Nogueira, Grafos Split e Grafos Split Generalizados, Master Thesis, COPPE-Sistemas, Universidade Federal do Rio de Janeiro, Brazil, 1999 (in Portuguese).; L.T. Nogueira, Grafos Split e Grafos Split Generalizados, Master Thesis, COPPE-Sistemas, Universidade Federal do Rio de Janeiro, Brazil, 1999 (in Portuguese).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.