Delphi.science

Clique partitions and distinct color sets in list colorings

Source: arxiv.org/abs/2611.07924

Jun Yue

arXivarxiv/2611.07924Nov 5, 2026math.COscore 0

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…

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.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}'