Brambles and independent packings in chordal graphs

DOI10.1016/j.disc.2008.05.031zbMath1218.05110OpenAlexW2046755592MaRDI QIDQ1045070

Kathie Cameron

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.05.031

zbMATH Keywords

independent setcliquechordal graphinduced matchingmin-max theorembrambleindependent packing

Mathematics Subject Classification ID

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

Related Items (6)

Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• Packing \(r\)-cliques in weighted chordal graphs
• Induced matchings in bipartite graphs
• Treewidth lower bounds with brambles
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Maximum induced matchings of random cubic graphs
• 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
• Finding a maximum induced matching in weakly chordal graphs
• Partitioning chordal graphs into independent sets and cliques
• A characterisation of rigid circuit graphs
• On maximum induced matchings in bipartite graphs
• New results on induced matchings
• A characterization of perfect graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The graphs with maximum induced matching and maximum matching the same size
• Independent packings in structured graphs
• Representations of chordal graphs as subtrees of a tree
• Graph Classes: A Survey
• Bipartite Domination and Simultaneous Matroid Covers
• Induced matchings in cubic graphs
• Particionamento de Grafos Cordais em Conjuntos Independentes e Cliques

This page was built for publication: Brambles and independent packings in chordal graphs