Weak Degeneracy with Availability for Planar Graphs
Source: arxiv.org/abs/2611.25850
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…
Comments and reviews
No comments yet.
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}'