{"ID":6497724,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09309","arxiv_id":"2607.09309","title":"A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting","abstract":"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.","short_abstract":"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 nonedg...","url_abs":"https://arxiv.org/abs/2607.09309","url_pdf":"https://arxiv.org/pdf/2607.09309v1","authors":"[\"Amir Ali Ahmadi\",\"Pravesh K. Kothari\",\"Yukai Tang\"]","published":"2026-07-10T11:46:33Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"math.CO\",\"math.OC\"]","methods":"[]","has_code":false}