Graph Coloring via Clique Search with Symmetry Breaking
Open Access
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.Keywords
Funding Information
- Nemzeti Kutatási és Technológiai Hivatal (SNN-135643)
This publication has 20 references indexed in Scilit:
- An exact approach for the Vertex Coloring ProblemDiscrete Optimization, 2011
- Parallel algorithms for finding cliques in a graphJournal of Physics: Conference Series, 2011
- A one-to-one correspondence between colorings and stable setsOperations Research Letters, 2008
- Cliques, holes and the vertex coloring polytopeInformation Processing Letters, 2004
- A fast algorithm for the maximum clique problemDiscrete Applied Mathematics, 2002
- Finding all k-cliques in k-partite graphs, an application in textile engineeringComputers & Operations Research, 2002
- An exact algorithm for the maximum clique problemOperations Research Letters, 1990
- A combinatorial approach for Keller's conjecturePeriodica Mathematica Hungarica, 1990
- New methods to color the vertices of a graphCommunications of the ACM, 1979
- Algorithm 457: finding all cliques of an undirected graphCommunications of the ACM, 1973