Partitioning chordal graphs into independent sets and cliques

DOI10.1016/S0166-218X(03)00371-8zbMath1043.05097OpenAlexW2141942969MaRDI QIDQ1827861

Sulamita Klein, Fábio Protti, Loana Tito Nogueira, Pavol Hell

Publication date: 6 August 2004

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00371-8

zbMATH Keywords

Chordal graphsSplit graphsGreedy algorithmsList partitionsMin-max theoremsPre-colouring extension

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (39)

Clique cycle-transversals in distance-hereditary graphs ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ A Brooks‐Type Theorem for the Bichromatic Number ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ Cover-incomparability graphs and chordal graphs ⋮ Obstructions to partitions of chordal graphs ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques ⋮ Extended skew partition problem ⋮ Matrix partitions of perfect graphs ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ Partitioning extended \(P_4\)-laden graphs into cliques and stable sets ⋮ Colouring, constraint satisfaction, and complexity ⋮ \((k,l)\)-colourings and Ferrers diagram representations of cographs ⋮ Edge clique partition in \((k,\ell)\)-graphs ⋮ Strict chordal and strict split digraphs ⋮ Polarity of chordal graphs ⋮ Stable-\(\Pi\) partitions of graphs ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs ⋮ A note on the bichromatic numbers of graphs ⋮ On split-coloring problems ⋮ Graph partitions with prescribed patterns ⋮ Join colourings of chordal graphs ⋮ On Injective Colourings of Chordal Graphs ⋮ On 2-Subcolourings of Chordal Graphs ⋮ Distance paired-domination problems on subclasses of chordal graphs ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Brambles and independent packings in chordal graphs ⋮ Partitioning graphs into complete and empty graphs ⋮ Partitioning cographs into cliques and stable sets ⋮ Minimal obstructions for a matrix partition problem in chordal graphs ⋮ Independent packings in structured graphs ⋮ Characterizing –partitionable Cographs ⋮ Matrix Partitions with Finitely Many Obstructions ⋮ Packing \(r\)-cliques in weighted chordal graphs ⋮ List matrix partitions of chordal graphs ⋮ \((p,k)\)-coloring problems in line graphs

Cites Work

• The complexity of some problems related to GRAPH 3-COLORABILITY
• \(r\)-dominating cliques in graphs with hypertree structure
• Extending graph colorings
• Partitions of graphs into one or two independent sets and cliques
• Complexity of graph partition problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Partitioning chordal graphs into independent sets and cliques