Weighted colouring of hexagonal graphs.

Definitions and mathematical statement

Let $e_1=(1,0)$ and $e_2=(1/2,\sqrt3/2)$. The triangular lattice has vertices $ae_1+be_2$ for $a,b\in\mathbb Z$ and joins pairs at Euclidean distance one. A hexagonal graph in this problem is a finite induced subgraph of that lattice: once its vertex set is chosen, every lattice edge between selected vertices is retained. This terminology does not mean a subgraph of the degree-three honeycomb lattice.

Give each vertex a positive integer demand $p(v)$. A multicoloring with $k$ colors assigns a set $C(v)\subseteq\{1,\ldots,k\}$ of exactly $p(v)$ labels to each vertex, with $C(u)\cap C(v)=\varnothing$ whenever $uv$ is an edge. Let $\chi(G,p)$ be the smallest such $k$. Define the weighted clique number by \[ \omega(G,p)=\max\left\{\sum_{v\in Q}p(v):Q\subseteq V(G) \text{ is a clique}\right\}, \] where a clique has all its distinct pairs adjacent; singleton cliques are included.

The conjecture is that there exists an absolute constant $c\ge0$ such that every hexagonal graph and every positive integer demand function satisfy \[ \chi(G,p)\le\tfrac98\omega(G,p)+c. \] The additive constant is independent of both graph size and demand magnitudes. Demands specify distinct colors within each vertex, rather than weights in an ordinary one-color assignment. No triangle-free assumption is made in this main conjecture, and triangles contribute their full combined demand to the clique lower bound.

Short English statement

Can every demanded multicoloring of an induced triangular-lattice graph be achieved within nine-eighths of its weighted clique bound plus a universal constant?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3247 (OPG-47511), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Weighted colouring of hexagonal graphs.. Original problem and discussion. http://www.openproblemgarden.org/op/weighted_colouring_of_hexagonal_graphs.