Computing the chromatic number of a graph is an NP-hard problem. For random graphs and some other classes of graphs, estimators of the expected chromatic number have been well studied. In this paper, a new 0–1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program.

On the chromatic number of graphs / Festa, Paola; S., Butenko; P. M., Pardalos. - In: JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS. - ISSN 0022-3239. - 109:1(2001), pp. 51-67.

On the chromatic number of graphs

FESTA, PAOLA;
2001

Abstract

Computing the chromatic number of a graph is an NP-hard problem. For random graphs and some other classes of graphs, estimators of the expected chromatic number have been well studied. In this paper, a new 0–1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program.
2001
On the chromatic number of graphs / Festa, Paola; S., Butenko; P. M., Pardalos. - In: JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS. - ISSN 0022-3239. - 109:1(2001), pp. 51-67.
File in questo prodotto:
File Dimensione Formato  
a4_chromatic_number.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Accesso privato/ristretto
Dimensione 173.26 kB
Formato Adobe PDF
173.26 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: https://hdl.handle.net/11588/144803
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact