2024/12/13 by Sina Ghasemi Nezhad, Nezhad, Sina Ghasemi, Maryam Moghaddas +3
Computer Science · #68W05 #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2412.10082
openalex publication_date 2024/12/13 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
In this paper, we investigate the \Grundy Coloring problem for graphs\nwith a cluster modulator, a structure commonly found in dense graphs. The\nGrundy chromatic number, representing the maximum number of colors needed for\nthe first-fit coloring of a graph in the worst-case vertex ordering, is known\nto be W[1]-hard when parameterized by the number of colors required by the\nmost adversarial ordering. We focus on fixed-parameter tractable (FPT)\nalgorithms for solving this problem on graph classes characterized by dense\nsubstructures, specifically those with a cluster modulator. A cluster modulator\nis a vertex subset whose removal results in a cluster graph (a disjoint union\nof cliques). We present FPT algorithms for graphs where the cluster graph\nconsists of one, two, or k cliques, leveraging the cluster modulator's\nproperties to achieve the best-known FPT runtimes, parameterized by both the\nmodulator's size and the number of cliques.\n