Graph Coloring Below Guarantees via Co-Triangle Packing
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908540575154176 |
|---|---|
| author | Akmal, Shyan Koana, Tomohiro |
| author_facet | Akmal, Shyan Koana, Tomohiro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_12347 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph Coloring Below Guarantees via Co-Triangle Packing Akmal, Shyan Koana, Tomohiro Data Structures and Algorithms Discrete Mathematics 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. |
| title | Graph Coloring Below Guarantees via Co-Triangle Packing |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2509.12347 |