Vortrag: Strengthening of the semidefinite relaxation for graph coloring probl...
Stammdaten
Titel: | Strengthening of the semidefinite relaxation for graph coloring problem |
Beschreibung: | Let G = (V, E) be a graph with |V| = n. The chromatic number χ(G) is the smallest t such that vertices of G can be partitioned into t stable sets. Let S = (s1, …, sk) be a matrix where each column si represents a stable set vector and where the corresponding stable sets partition vertices into k sets. The n × n matrix X = SST is called coloring matrix. Now let I ⊆ V be a subset of vertices of G. We denote by GI the subgraph that is induced by the set of vertices I, and by XI = (Xi,j) i,j ∈I the submatrix of X which is indexed by I. In our work we consider subgraphs GI with I = {1, …, k + 1} such that vertices {1, …, k} form a clique C, and vertex k + 1 is not adjacent to all vertices in C, and we show that the inequality Σ i∈C Xi,k+1 ≤ 1 holds for any coloring matrix XI . Furthermore, we introduce respective inequalities into the semidefinite relaxation and show that the Lovász theta number can be strengthened. Finally, we compare our bounds with relaxations given by Szegedy and Meurdesoif and present computational results. |
Schlagworte: |
Typ: | Angemeldeter Vortrag |
Homepage: | https://hdoi.hr/koi-2022/ |
Veranstaltung: | KOI 2022, 19th International Conference on Operational Research (Šibenik) |
Datum: | 28.09.2022 |
Vortragsstatus: | stattgefunden (Präsenz) |
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Vortragsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
TeilnehmerInnenkreis |
|
Publiziert? |
|
Arbeitsgruppen |
|
Kooperationen
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte |
|
Publikationen | Keine verknüpften Publikationen vorhanden |
Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
Vorträge | Keine verknüpften Vorträge vorhanden |