2 citations · 4 across the 7 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
cs.DS2025
Graph Coloring Below Guarantees via Co-Triangle Packing
Shyan Akmal, Tomohiro Koana
In the -Coloring Problem, we are given a graph on nodes, and tasked with determining if its vertices can be properly colored using colors. In this paper we study b…
cs.DS2025
A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Amir Abboud, Shyan Akmal, Nick Fischer
We present the first truly subcubic, combinatorial algorithm for detecting an induced -cycle in a graph. The running time is on -node graphs, thus separating th…
cs.DS2025
Faster Edge Coloring by Partition Sieving
Shyan Akmal, Tomohiro Koana
In the Edge Coloring problem, we are given an undirected graph with vertices and edges, and are tasked with finding the smallest positive integer so that the edges…