--- title: [2607.25973] k-Coloring is Faster than Computing the... description: A new research paper proves that k-coloring on n-vertex graphs admits a randomized algorithm running in time (2−ε_k)^n for every fixed k, where ε_k > 0. This... canonical: https://daily.dev/posts/2607-25973-k-coloring-is-faster-than-computing-the-chromatic-number-b6vvcikdy twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: [2607.25973] k-Coloring is Faster than Computing the Chromatic Number | daily.dev og:description: A new research paper proves that k-coloring on n-vertex graphs admits a randomized algorithm running in time (2−ε_k)^n for every fixed k, where ε_k > 0. This... og:url: https://daily.dev/posts/2607-25973-k-coloring-is-faster-than-computing-the-chromatic-number-b6vvcikdy og:image: https://api.daily.dev/og/posts/b6vVcikdy.png og:image:alt: [2607.25973] k-Coloring is Faster than Computing the Chromatic Number og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # [2607.25973] k-Coloring is Faster than Computing the Chromatic Number **[Hacker News](https://daily.dev/sources/hn)** · 2 min read · 0 upvotes · 0 comments ## Summary A new research paper proves that k-coloring on n-vertex graphs admits a randomized algorithm running in time (2−ε_k)^n for every fixed k, where ε_k > 0. This resolves a long-standing open problem: previously, only k ≤ 6 were known to be strictly faster than the general O*(2^n) chromatic number algorithm by Björklund, Husfeldt, and Koivisto (SICOMP 2009). The result is achieved by combining a (k+2)-coloring to k-list-coloring reduction with a hypergraph-containers approach, plus new algorithms for list-coloring instances with mixed color list lengths, yielding an iterable reduction from (k+1)-list-coloring to k-list-coloring over fixed palettes. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### What was the previous best known time complexity for k-coloring on n-vertex graphs before this result? Before this result, only k ≤ 6 were known to have algorithms strictly faster than O*(2^n). The general O*(2^n) algorithm by Björklund, Husfeldt, and Koivisto (SICOMP 2009) computes the chromatic number and was the best known bound for k > 6. The new result gives a randomized algorithm in time (2−ε_k)^n for every fixed k, where ε_k > 0. _Researchers working on graph algorithm complexity find related breakthroughs faster on daily.dev._ ## Similar posts on daily.dev - [A quick look at zero-knowledge proofs](https://daily.dev/posts/a-quick-look-at-zero-knowledge-proofs-u8pvjyhpf) · Programming Digest · 0 upvotes · 0 comments - [Graph Coloring You Can See](https://daily.dev/posts/graph-coloring-you-can-see-iuk0aslhm) · Towards Data Science · 0 upvotes · 0 comments - [Creating a Color Palette from an Image — Amanda Hinton](https://daily.dev/posts/creating-a-color-palette-from-an-image-amanda-hinton-xk9e9debm) · Hacker News · 0 upvotes · 0 comments - [Colourfields](https://daily.dev/posts/colourfields-bflskiyju) · Arthur O'Dwyer · 0 upvotes · 0 comments - [Ordered Dithering with Arbitrary or Irregular Colour Palettes](https://daily.dev/posts/ordered-dithering-with-arbitrary-or-irregular-colour-palettes-zkohxicmj) · Lobsters · 1 upvotes · 0 comments --- Tags: [#algorithms](https://daily.dev/tags/algorithms) [View this post on daily.dev](https://daily.dev/posts/2607-25973-k-coloring-is-faster-than-computing-the-chromatic-number-b6vvcikdy) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"[2607.25973] k-Coloring is Faster than Computing the Chromatic Number","url":"https://daily.dev/posts/2607-25973-k-coloring-is-faster-than-computing-the-chromatic-number-b6vvcikdy","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/2607-25973-k-coloring-is-faster-than-computing-the-chromatic-number-b6vvcikdy"},"datePublished":"2026-08-08T19:22:50.539Z","dateModified":"2026-08-08T19:23:13.044Z","description":"A new research paper proves that k-coloring on n-vertex graphs admits a randomized algorithm running in time (2−ε_k)^n for every fixed k, where ε_k > 0. This...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/1fed0de190485cbbb37a86fdf656d71b?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/1fed0de190485cbbb37a86fdf656d71b?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Hacker News","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Hacker News","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/hn","url":"https://daily.dev/sources/hn"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/2607-25973-k-coloring-is-faster-than-computing-the-chromatic-number-b6vvcikdy","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"algorithms","timeRequired":"PT2M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Hacker News","item":"https://daily.dev/sources/hn"},{"@type":"ListItem","position":3,"name":"[2607.25973] k-Coloring is Faster than Computing the Chromatic Number"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/2607-25973-k-coloring-is-faster-than-computing-the-chromatic-number-b6vvcikdy#faq","mainEntity":[{"@type":"Question","name":"What was the previous best known time complexity for k-coloring on n-vertex graphs before this result?","acceptedAnswer":{"@type":"Answer","text":"Before this result, only k ≤ 6 were known to have algorithms strictly faster than O*(2^n). The general O*(2^n) algorithm by Björklund, Husfeldt, and Koivisto (SICOMP 2009) computes the chromatic number and was the best known bound for k > 6. The new result gives a randomized algorithm in time (2−ε_k)^n for every fixed k, where ε_k > 0. Researchers working on graph algorithm complexity find related breakthroughs faster on daily.dev."}}]} ```