Clique partitions and distinct color sets in list colorings
Source: arxiv.org/abs/2611.07924
For an \(n\)-vertex graph \(G\) and an integer \(m\ge n\), let \(f'(G,m)\) be the minimum number of distinct color sets used by proper colorings from \(m\)-element lists that are disjoint at distinct nonadjacent vertices. A clique-partition assignment gives a common list to the vertices of each part of a clique partition and uses disjoint lists on different parts. In this paper, we construct a graph on \(20\) vertices for which these assignments do not attain \(f'(G,20)\), and a fixed graph on \(25\) vertices for which they fail to attain the minimum for every allowed list size. For every…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.07924
curl -X POST /api/v1/records/arxiv/2611.07924/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.07924/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'