Brambles and independent packings in chordal graphs |
| |
Authors: | Kathie Cameron |
| |
Affiliation: | Department of Mathematics, Wilfrid Laurier University, Waterloo, Ontario, Canada N2L 3C5 |
| |
Abstract: | ![]() 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. |
| |
Keywords: | Independent packing Induced matching Bramble Chordal graph Min-max theorem Independent set Clique |
本文献已被 ScienceDirect 等数据库收录! |
|