Delphi.science

Weak Degeneracy with Availability for Planar Graphs

Source: arxiv.org/abs/2611.25850

Zdeněk Dvořák, Evelyne Smith-Roberge

arXivarxiv/2611.25850Nov 19, 2026math.COscore 0

Every planar graph admits exponentially many proper colorings for any assignment of lists of five allowed colors to its vertices. In this paper, we show that very little beyond degeneracy is needed to prove that this statement holds. In particular, given a planar graph G (but not the list assignment), our argument provides an algorithm consisting entirely of instructions of the following form: ``Color the vertex v using any color c from its list, and remove c from the lists of neighbors of v.'' and ``For the edge uv, choose any k colors from the list of u, then color v by any color c from…

JSONText

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