BibTeX
@INPROCEEDINGS{
         Bucker2025HGC,
       author = "H. M. B{\"u}cker and C. Komusiewicz and J. Rostalsky",
       title = "Heuristic Graph Colouring using Hypergraph Representations",
       booktitle = "2025 Proceedings of the Conference on Applied and Computational Discrete
         Algorithms (ACDA), July~30--August~1, 2025",
       editor = "A. Conway and A. Pothen and M. Farach-Colton and B. U{\c{c}}ar",
       pages = "208--221",
       address = "Philadelphia, PA, USA",
       publisher = "SIAM",
       url = "https://doi.org/10.1137/1.9781611978759.16",
       doi = "10.1137/1.9781611978759.16",
       abstract = "We revisit the classic Graph Colouring problem in the context of column
         partitioning of matrices. In this context, we are given a hypergraph and the aim is to colour the
         vertices of the hypergraph by a minimum number of colours such that in each hyperedge every colour
         occurs at most once. We provide a comprehensive implementation and experimental evaluation of
         combinations of known heuristical techniques such as vertex orderings for greedy colouring, vertex
         reordering after an initial colouring, and recolouring of vertices to save colours. In addition, we
         provide a new stronger recolouring method that is based on the hypergraph view of the problem. Our
         implementation is specifically tailored towards efficiency on hypergraph instances. We compare our
         implementation with the ColPack library and find that several heuristics not contained in ColPack
         yield solutions with fewer colours at the cost of higher but still affordable running times. We
         complement these results by a theoretical analysis of the problem complexity on hypergraphs that can
         be covered by few hyperedges.",
       year = "2025",
       ad_tools = "ColPack, SciCol",
       ad_theotech = "graph coloring"
}