Vertex Partitions of Graphs into Cographs and Stars

DOI10.1002/jgt.21724zbMath1280.05104OpenAlexW1495584351MaRDI QIDQ2874091

Mickaël Montassier, Pascal Ochem, Paul Dorbec

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

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

Related Items (4)

The adjacency matrix of a graph as a data table: a geometric perspective ⋮ On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions ⋮ On the computational complexity of the bipartizing matching problem ⋮ On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions

Cites Work

• Partitions of graphs into cographs
• On \(P_4\)-transversals of chordal graphs
• The complexity of \(G\)-free colourability
• List strong linear 2-arboricity of sparse graphs
• A Linear Recognition Algorithm for Cographs
• Improper choosability of graphs and maximum average degree
• Unnamed Item

This page was built for publication: Vertex Partitions of Graphs into Cographs and Stars