Open Research Index

A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting

Amir Ali Ahmadi, Pravesh K. Kothari, Yukai Tang

arXivarxiv/2607.09309Jul 10, 2026cs.DSscore 0

We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perfect graph contains a clique of a given size by iteratively counting walks in the graph with certain weights assigned to its edges and nonedges. These weights are initialized according to a uniform scheme and then updated in each iteration based on the walk counts from the previous iteration.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.09309
curl -X POST /api/v1/records/arxiv/2607.09309/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09309/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'