Partitioning extended \(P_4\)-laden graphs into cliques and stable sets

DOI10.1016/j.ipl.2012.07.011zbMath1248.05153OpenAlexW2088316879MaRDI QIDQ456142

Sulamita Klein, Raquel S. F. Bravo, Fábio Protti, Rudini Menezes Sampaio, Loana Tito Nogueira

Publication date: 23 October 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.07.011

zbMATH Keywords

graph algorithmscliquesgraph partition\((k\(P_{4}\)-laden graphs\ell )\)-cocoloring\ell )\)-graphs

Mathematics Subject Classification ID

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

Related Items (5)

PSPACE-hardness of two graph coloring games ⋮ Perfect matching cuts partitioning a graph into complementary subgraphs ⋮ PSPACE-completeness of two graph coloring games ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ Partitioning a graph into disjoint cliques and a triangle-free graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the \(b\)-coloring of \(P_{4}\)-tidy graphs
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• On split-coloring problems
• The complexity of some problems related to GRAPH 3-COLORABILITY
• \(P_{4}\)-laden graphs: A new class of brittle graphs
• Partitioning chordal graphs into independent sets and cliques
• Matrix partitions of perfect graphs
• Partitioning cographs into cliques and stable sets
• Chromatic number versus chromatic number in graphs with bounded clique number
• Characterizing –partitionable Cographs
• Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing
• Some extremal results in cochromatic and dichromatic theory

This page was built for publication: Partitioning extended \(P_4\)-laden graphs into cliques and stable sets