Vertex partitions of graphs into cographs and stars

DOI10.1002/JGT.21724MaRDI QIDQ2874091zbMATH OpenOpenAlexFDO

Authors Paul Dorbec, Mickaël Montassier, Pascal Ochem

Publication date 28 January 2014

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.21724

zbMATH Keywords

NP-completenesscoloringscograph partition

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Partitions of graphs into cographs
• Polar cographs
• Characterizing –partitionable Cographs
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Partitioning cographs into two forests and one independent set

Cites work

• scientific article; zbMATH DE number 866055 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• Improper choosability of graphs and maximum average degree
• List strong linear 2-arboricity of sparse graphs
• On \(P_4\)-transversals of chordal graphs
• Partitions of graphs into cographs
• The complexity of \(G\)-free colourability

Cited in

(12)

• Characterizing –partitionable Cographs
• On the computational complexity of the bipartizing matching problem
• Partitioning cographs into two forests and one independent set
• Excluding pairs of graphs
• Cographs whose complements consist of \(k\)-partite components
• Partitions of graphs into cographs
• Generalizing cographs to 2-cographs
• The adjacency matrix of a graph as a data table: a geometric perspective
• Partitioning a graph into disjoint cliques and a triangle-free graph
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• Co-2-plex vertex partitions
• On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions

This page was built for publication: Vertex partitions of graphs into cographs and stars

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