Monopolar graphs: complexity of computing classical graph parameters

DOI10.1016/J.DAM.2020.12.023MaRDI QIDQ2659081zbMATH OpenOpenAlexFDO

Authors Michele Barbato, Dario Bezzi

Publication date 25 March 2021

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

Full work available at URL https://doi.org/10.1016/j.dam.2020.12.023

zbMATH Keywords

clique partitioningcomputational complexitygraph coloringmaximum-weight cliquemonopolar graphstable set

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• Complexity and algorithms for recognizing polar and monopolar graphs
• On the Polarity and Monopolarity of Graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Uniquely monopolar-partitionable block graphs
• List monopolar partitions of claw-free graphs

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithms for unipolar and generalized split graphs
• Clustering and domination in perfect graphs
• Complexity and algorithms for recognizing polar and monopolar graphs
• Complexity results on graphs with few cliques
• Dominating sets for split and bipartite graphs
• Graph theory
• scientific article; zbMATH DE number 3977053 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Line-Polar Graphs: Characterization and Recognition
• On clique partitions of split graphs
• On NP-hardness of the clique partition -- independence number gap recognition and related problems
• On the Polarity and Monopolarity of Graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Polar graphs and maximal independent sets
• Polar permutation graphs
• Polarity of chordal graphs
• Solving partition problems with colour-bipartitions
• Some simplified NP-complete graph problems
• The NP-completeness of (1,r)-subcolorability of cubic graphs
• Trivially perfect graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

Cited in

(4)

• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Complexity of edge monitoring on some graph classes
• List monopolar partitions of claw-free graphs
• On the Polarity and Monopolarity of Graphs

This page was built for publication: Monopolar graphs: complexity of computing classical graph parameters

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