{"ID":2871091,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.12347","arxiv_id":"2509.12347","title":"Graph Coloring Below Guarantees via Co-Triangle Packing","abstract":"In the $\\ell$-Coloring Problem, we are given a graph on $n$ nodes, and tasked with determining if its vertices can be properly colored using $\\ell$ colors. In this paper we study below-guarantee graph coloring, which tests whether an $n$-vertex graph can be properly colored using $g-k$ colors, where $g$ is a trivial upper bound such as $n$. We introduce an algorithmic framework that builds on a packing of co-triangles $\\overline{K_3}$ (independent sets of three vertices): the algorithm greedily finds co-triangles and employs a win-win analysis. If many are found, we immediately return YES; otherwise these co-triangles form a small co-triangle modulator, whose deletion makes the graph co-triangle-free. Extending the work of [Gutin et al., SIDMA 2021], who solved $\\ell$-Coloring (for any $\\ell$) in randomized $O^*(2^{k})$ time when given a $\\overline{K_2}$-free modulator of size $k$, we show that this problem can likewise be solved in randomized $O^*(2^{k})$ time when given a $\\overline{K_3}$-free modulator of size~$k$. This result in turn yields a randomized $O^{*}(2^{3k/2})$ algorithm for $(n-k)$-Coloring (also known as Dual Coloring), improving the previous $O^{*}(4^{k})$ bound. We then introduce a smaller parameterization, $(ω+\\overlineμ-k)$-Coloring, where $ω$ is the clique number and $\\overlineμ$ is the size of a maximum matching in the complement graph; since $ω+\\overlineμ\\le n$ for any graph, this problem is strictly harder. Using the same co-triangle-packing argument, we obtain a randomized $O^{*}(2^{6k})$ algorithm, establishing its fixed-parameter tractability for a smaller parameter. Complementing this finding, we show that no fixed-parameter tractable algorithm exists for $(ω-k)$-Coloring or $(\\overlineμ-k)$-Coloring under standard complexity assumptions.","short_abstract":"In the $\\ell$-Coloring Problem, we are given a graph on $n$ nodes, and tasked with determining if its vertices can be properly colored using $\\ell$ colors. In this paper we study below-guarantee graph coloring, which tests whether an $n$-vertex graph can be properly colored using $g-k$ colors, where $g$ is a trivial up...","url_abs":"https://arxiv.org/abs/2509.12347","url_pdf":"https://arxiv.org/pdf/2509.12347v1","authors":"[\"Shyan Akmal\",\"Tomohiro Koana\"]","published":"2025-09-15T18:19:48Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}