×

Brambles and independent packings in chordal graphs. (English) Zbl 1218.05110

Summary: An independent packing of triangles is a set of pairwise disjoint triangles, no two of which are joined by an edge. A triangle bramble is a set of triangles, every pair of which intersect or are joined by an edge. More generally, I consider independent packings and brambles of any specified connected graphs, not just triangles. I give a min-max theorem for the maximum number of graphs in an independent packing of any family of connected graphs in a chordal graph, and a dual min-max theorem for the maximum number of graphs in a bramble in a chordal graph.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bellenbaum, Patrick; Diestel, Reinhard, Two short proofs concerning tree decompositions, Combinatorics, Probability and Computing, 11, 541-547 (2002) · Zbl 1018.05081
[2] Berge, Claude, Les problèmes de colorations en théorie des graphs, Publications Institut Statist. University Paris, 9, 123-160 (1960) · Zbl 0103.16201
[3] Bodlaender, Hans; Grigoriev, Alexander; Koster, Arie, Treewidth lower bounds with brambles, Algorithmica, 51, 81-98 (2008) · Zbl 1138.68065
[4] Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P., Graph Classes - A Survey (1999), SIAM Publications: SIAM Publications Philadelphia, PA · Zbl 0919.05001
[5] Buneman, P., A characterization of rigid circuit graphs, Discrete Mathematics, 9, 205-212 (1974) · Zbl 0288.05128
[6] Cameron, Kathie, Induced matchings, Discrete Applied Mathematics, 24, 97-102 (1989) · Zbl 0687.05033
[7] Cameron, Kathie, Induced matchings in intersection graphs, Discrete Mathematics, 278, 1-9 (2003) · Zbl 1033.05080
[8] Cameron, Kathie; Hell, Pavol, Independent packings in structured graphs, Mathematical Programming Series B, 105, 201-213 (2006) · Zbl 1078.05067
[9] Cameron, K.; Sritharan, R.; Tang, Y., Finding a maximum induced matching in weakly chordal graphs, Discrete Mathematics, 266, 133-142 (2003) · Zbl 1022.05064
[10] Cameron, K.; Walker, T. L., The graphs with maximum matching and maximum induced matching the same size, Discrete Mathematics, 299, 49-55 (2005) · Zbl 1073.05054
[11] Chang, Jou-Ming, Induced matchings in asteroidal-triple free graphs, Discrete Applied Mathematics, 132, 67-78 (2003) · Zbl 1029.05120
[12] Duckworth, W.; Wormald, N. C.; Zito, M., Maximum induced matchings of random cubic graphs, Journal of Computational and Applied Mathematics, 142, 39-50 (2002) · Zbl 1001.05093
[13] Faudree, R. J.; Gyárfás, A.; Schelp, R. H.; Tuza, Zs., Induced matchings in bipartite graphs, Discrete Mathematics, 78, 83-87 (1989) · Zbl 0709.05026
[14] Fricke, G.; Laskar, R. C., Strong matchings on trees, Congressus Numerantium, 89, 239-243 (1992) · Zbl 0786.05065
[15] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, SIAM Journal on Computing, 1, 47-56 (1972) · Zbl 0266.05101
[16] Golumbic, M. C.; Laskar, R. C., Irredundancy in circular-arc graphs, Discrete Applied Mathematics, 44, 79-89 (1993) · Zbl 0783.05059
[17] Golumbic, M. C.; Lewenstein, M., New results on induced matchings, Discrete Applied Mathematics, 101, 157-165 (2000) · Zbl 0951.68104
[18] Hajnal, A.; Surányi, J., Über die Auflösung von Graphen in vollständige Teilgraphen, Ann. University Sci. Budapest, Eötvös, Sect. Math, 1, 113-121 (1958) · Zbl 0093.37801
[19] Hell, P.; Klein, S.; Protti, F.; Tito, L., On generalized split graphs, Electronic Notes in Discrete Mathematics, 7 (2001) · Zbl 0981.05076
[20] P. Hell, S. Klein, L.T. Nogueira, F. Protti, Independent \(K_r\); P. Hell, S. Klein, L.T. Nogueira, F. Protti, Independent \(K_r\) · Zbl 1208.05111
[21] Hell, P.; Klein, S.; Tito-Nogueira, L.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Applied Mathematics, 185-194 (2004) · Zbl 1043.05097
[22] Hell, P.; Klein, S.; Tito-Nogueira, L.; Protti, F., Packing \(r\)-cliques in weighted chordal graphs, Annals of Operations Research, 138, 179-187 (2005) · Zbl 1091.90073
[23] Horák, P.; He, Q.; Trotter, W. T., Induced matchings in cubic graphs, Journal of Graph Theory, 17, 151-160 (1993) · Zbl 0787.05038
[24] Ko, C. W.; Shepherd, F. B., Bipartite domination and simultaneous matroid covers, SIAM Journal on Discrete Mathematics, 16, 327-349 (2003) · Zbl 1029.05097
[25] Kobler, D.; Rotics, U., Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size, Algorithmica, 37, 327-346 (2003) · Zbl 1082.68592
[26] Lovász, László, A characterization of perfect graphs, Journal of Combinatorial Theory B, 13, 95-98 (1972) · Zbl 0241.05107
[27] Lozin, V. V., On maximum induced matchings in bipartite graphs, Information Processing Letters, 81, 7-11 (2002) · Zbl 1046.68081
[28] Reed, B. A., Tree width and tangles: a new connectivity measure and some applications, (Surveys in Combinatorics, 1997 (London). Surveys in Combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser., vol. 241 (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 87-162 · Zbl 0895.05034
[29] Stockmeyer, L. J.; Vazirani, V. V., NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters, 15, 14-19 (1982) · Zbl 0493.68039
[30] Walter, J. R., Representations of chordal graphs as subtrees of a tree, Journal of Graph Theory, 2, 265-267 (1978) · Zbl 0441.05022
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.