A total coloring of a graph G=(V,E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive different colors. Any valid total coloring induces a partition of the elements of G into total matchings, which are defined as subsets of vertices and edges that can take the same color. In this paper, we propose Integer Linear Programming models for both the Total Coloring and the Total Matching problems, and we study the strength of the corresponding Linear Programming relaxations. The total coloring is formulated as the problem of finding the minimum number of total matchings that cover all the graph elements. This covering formulation can be solved by a Column Generation algorithm, where the pricing subproblem corresponds to the Weighted Total Matching Problem. Hence, we study the Total Matching Polytope. We introduce three families of nontrivial valid inequalities: vertex-clique inequalities based on standard clique inequalities of the Stable Set Polytope, congruent-2k3 cycle inequalities based on the parity of the vertex set induced by the cycle, and even-clique inequalities induced by complete subgraphs of even order. We prove that congruent-2k3 cycle inequalities are facet-defining only when k=4, while the vertex-clique and even-cliques are always facet-defining. Finally, we present preliminary computational results of a Column Generation algorithm for the Total Coloring Problem and a Cutting Plane algorithm for the Total Matching Problem.

Ferrarini, L., Gualandi, S. (2022). Total Coloring and Total Matching: Polyhedra and Facets. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 303(1), 129-142 [10.1016/j.ejor.2022.02.025].

Total Coloring and Total Matching: Polyhedra and Facets

Ferrarini, L
;
2022

Abstract

A total coloring of a graph G=(V,E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive different colors. Any valid total coloring induces a partition of the elements of G into total matchings, which are defined as subsets of vertices and edges that can take the same color. In this paper, we propose Integer Linear Programming models for both the Total Coloring and the Total Matching problems, and we study the strength of the corresponding Linear Programming relaxations. The total coloring is formulated as the problem of finding the minimum number of total matchings that cover all the graph elements. This covering formulation can be solved by a Column Generation algorithm, where the pricing subproblem corresponds to the Weighted Total Matching Problem. Hence, we study the Total Matching Polytope. We introduce three families of nontrivial valid inequalities: vertex-clique inequalities based on standard clique inequalities of the Stable Set Polytope, congruent-2k3 cycle inequalities based on the parity of the vertex set induced by the cycle, and even-clique inequalities induced by complete subgraphs of even order. We prove that congruent-2k3 cycle inequalities are facet-defining only when k=4, while the vertex-clique and even-cliques are always facet-defining. Finally, we present preliminary computational results of a Column Generation algorithm for the Total Coloring Problem and a Cutting Plane algorithm for the Total Matching Problem.
Articolo in rivista - Articolo scientifico
Combinatorial Optimization; Integer Programming; Total Coloring; Total Matching;
English
16-nov-2022
2022
303
1
129
142
reserved
Ferrarini, L., Gualandi, S. (2022). Total Coloring and Total Matching: Polyhedra and Facets. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 303(1), 129-142 [10.1016/j.ejor.2022.02.025].
File in questo prodotto:
File Dimensione Formato  
Ferrarini-2022-EJOR-VoR.pdf

Solo gestori archivio

Descrizione: File adatto a pubblicazione
Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Licenza: Tutti i diritti riservati
Dimensione 745.34 kB
Formato Adobe PDF
745.34 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/10281/402235
Citazioni
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
Social impact