2026-10-01T23:07:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24913 2026-09-23T23:20:38Z ddc:004 open_access

Graph Coloring Below Guarantees via Co-Triangle Packing Akmal, Shyan Koana, Tomohiro coloring parameterized algorithms algebraic algorithms above-guarantee below-guarantee subset convolution determinants In the 𝓁-Coloring problem, we are given a graph on n nodes, and tasked with determining if its vertices can be properly colored using 𝓁 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 K₃ (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 𝓁-Coloring (for any 𝓁) in randomized O^∗(2^k) time when given a K₂-free modulator of size k, we show that this problem can likewise be solved in randomized O^*(2^{k}) time when given a K₃-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, (ω+μ-k)-Coloring, where ω is the clique number and μ is the size of a maximum matching in the complement graph; since ω+μ ≤ 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 (μ-k)-Coloring under standard complexity assumptions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shyan Akmal and Tomohiro Koana 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.5 urn:nbn:de:0030-drops-249130 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode