A graph G = (V, E) is monopolar if V can be partitioned into a stable set and a set inducing the union of vertex-disjoint cliques. Motivated by an application of the clique partitioning problem on monopolar graphs to the cosmetic manufacturing, we study the complexity of computing classical graph parameters on the class of monopolar graphs. We show that computing the clique partitioning, stability and chromatic numbers of monopolar graphs is NP-hard. Conversely, we prove that every monopolar graph has a polynomial number of maximal cliques thus obtaining that a maximum-weight clique can be found in polynomial time on monopolar graphs.

Monopolar graphs: Complexity of computing classical graph parameters / M. Barbato, D. Bezzi. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 291(2021 Mar 11), pp. 277-285. [10.1016/j.dam.2020.12.023]

Monopolar graphs: Complexity of computing classical graph parameters

M. Barbato
Primo
;
D. Bezzi
Ultimo
2021-03-11

Abstract

A graph G = (V, E) is monopolar if V can be partitioned into a stable set and a set inducing the union of vertex-disjoint cliques. Motivated by an application of the clique partitioning problem on monopolar graphs to the cosmetic manufacturing, we study the complexity of computing classical graph parameters on the class of monopolar graphs. We show that computing the clique partitioning, stability and chromatic numbers of monopolar graphs is NP-hard. Conversely, we prove that every monopolar graph has a polynomial number of maximal cliques thus obtaining that a maximum-weight clique can be found in polynomial time on monopolar graphs.
Computational complexity; Monopolar graph; Maximum-weight clique; Clique partitioning; Stable set; Graph coloring
Settore MAT/09 - Ricerca Operativa
Advanced Cosmetic Manifacturing (AD-COM)
29-dic-2020
Article (author)
File in questo prodotto:
File Dimensione Formato  
Monopolar_Graphs_post_print.pdf

embargo fino al 29/12/2022

Descrizione: Articolo principale. Accepted paper con ulteriori correzioni fatte durante la proof-reading. Possibili discrepanze con la versione apparsa sulla rivista.
Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 346.43 kB
Formato Adobe PDF
346.43 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
1-s2.0-S0166218X20305485-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 559.76 kB
Formato Adobe PDF
559.76 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/804175
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact