Partitioning extended P₄-laden graphs into cliques and stable sets

DOI10.1016/J.IPL.2012.07.011zbMATH Open1248.05153OpenAlexW2088316879MaRDI QIDQ456142FDOQ456142

Authors: Raquel S. F. Bravo, Sulamita Klein, Fábio Protti, Loana T. Nogueira, Rudini M. Sampaio 

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

Recommendations

• Fixed-parameter algorithms for the cocoloring problem
• Two fixed-parameter algorithms for the cocoloring problem
• Partitioning cographs into cliques and stable sets
• On cocolourings and cochromatic numbers of graphs
• Partitions of graphs into cographs

zbMATH Keywords

graph partitiongraph algorithmscliques\((k\(P_{4}\)-laden graphs\ell )\)-cocoloring\ell )\)-graphs

Mathematics Subject Classification ID

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

Cites Work

• Partitioning chordal graphs into independent sets and cliques
• Characterizing –partitionable Cographs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• 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
• Matrix partitions of perfect graphs
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some extremal results in cochromatic and dichromatic theory
• \(P_{4}\)-laden graphs: A new class of brittle graphs
• Partitioning cographs into cliques and stable sets
• Chromatic number versus chromatic number in graphs with bounded clique number
• Generalized colouring (matrix partitions) of cographs
• Title not available (Why is that?)
• On split-coloring problems

Cited In (8)

• Two fixed-parameter algorithms for the cocoloring problem
• Fixed-parameter algorithms for the cocoloring problem
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• Perfect matching cuts partitioning a graph into complementary subgraphs
• Clique cycle transversals in graphs with few \(P_{4}\)'s
• PSPACE-hardness of two graph coloring games
• PSPACE-completeness of two graph coloring games

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456142)