Szabó, Sándor and Zaválnij, Bogdán (2022) Graph Coloring via Clique Search with Symmetry Breaking. SYMMETRY (BASEL), 14 (8). ISSN 2073-8994
|
Text
symmetry-14-01574-v2.pdf - Published Version Available under License Creative Commons Attribution. Download (344kB) | Preview |
Abstract
It is known that the problem of proper coloring of the nodes of a given graph can be reduced to finding cliques in a suitably constructed auxiliary graph. In this work, we explore the possibility of reducing the search space by exploiting the symmetries present in the auxiliary graph. The proposed method can also be used for efficient exact coloring of hyper graphs. We also precondition the auxiliary graph in order to further reduce the search space. We carry out numerical experiments to assess the practicality of these proposals. We solve some hard cases and prove a new lower limit of seven for the mycielski7 graph with the aid of the proposed technique.
| Item Type: | Article |
|---|---|
| Additional Information: | Cited By :1 Export Date: 29 March 2023 Correspondence Address: Zaválnij, B.; Rényi Institute of MathematicsHungary; email: bogdan@renyi.hu Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, SNN-135643 Funding text 1: This project was supported by the National Research, Development and Innovation Office—NKFIH Fund No. SNN-135643. |
| Uncontrolled Keywords: | Mathematical programming; Graph coloring; k-clique search; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 15 Jul 2025 10:59 |
| Last Modified: | 15 Jul 2025 10:59 |
| URI: | https://real.mtak.hu/id/eprint/221123 |
Actions (login required)
 |
Edit Item |
