Monopolar graphs: complexity of computing classical graph parameters

DOI10.1016/j.dam.2020.12.023OpenAlexW3116541381MaRDI QIDQ2659081

Dario Bezzi, Michele Barbato

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

computational complexitystable setgraph coloringclique partitioningmonopolar graphmaximum-weight clique

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for unipolar and generalized split graphs
• Solving partition problems with colour-bipartitions
• Dominating sets for split and bipartite graphs
• Polar graphs and maximal independent sets
• Polarity of chordal graphs
• Clustering and domination in perfect graphs
• On clique partitions of split graphs
• Some simplified NP-complete graph problems
• Trivially perfect graphs
• The NP-completeness of (1,r)-subcolorability of cubic graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• On NP-hardness of the clique partition -- independence number gap recognition and related problems
• Complexity and algorithms for recognizing polar and monopolar graphs
• Line-Polar Graphs: Characterization and Recognition
• Polar Permutation Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• On the Polarity and Monopolarity of Graphs

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