Weighted colouring of hexagonal graphs.

Discussion

A hexagonal graph is an induced subgraph of the triangular lattice. The triangular lattice $ TL $ may be described as follows. The vertices are all integer linear combinations $ a\mathbf{e_1} + b\mathbf{e_2} $ of the two vectors $ \mathbf{e_1}=(1,0) $ and $ \mathbf{e_2}=(\frac{1}{2}, \frac{\sqrt{3}}{2}) $ . Two vertices are adjacent when the Euclidean distance between them is 1. Let $ G $ be a graph and $ p $ a vertex weighting $ p:V(G)\rightarrow \mathbb{N} $ . The weighted clique number of $ (G,p) $ , denoted by $ \omega(G,p) $ , is the maximum weight of a clique, that is $ \max \{p(C) \tq C \mbox{ clique of } G\} $ , where $ p(C)=\sum_{v\in C} p(v) $ . A $ k $ -colouring of a $ (G,p) $ is a mapping $ C:V(G)\ra {\cal P}(\{1, \dots , k\}) $ such that for every vertex $ v\in V(G) $ , $ |C(v)|=p(v) $ and for all edge $ uv\in E(G) $ , $ C(u)\cap C(v)=\emptyset $ . The chromatic number of $ (G,p) $ , denoted by $ \chi(G,p) $ , is the least integer $ t $ such that $ (G,p) $ admits a $ t $ -colouring. The conjecture would be tight because of $ C_9 $ the cycle of length 9. The maximum size of stable set in $ C_9 $ is $ 4 $ . Thus $ \chi(C_9,\mathbf{k})\geq 9k/4 $ and $ \omega(G,\mathbf{k})=2k $ , where $ \mathbf{k} $ is the all $ k $ function. McDiarmid and Reed [MR] proved that $ \chi(G,p)\leq \frac{4\omega(G,p)+1}{3} $ for any hexagonal graph $ G $ and vertex weighting $ p $ . Havet [H] proved that if a hexagonal graph $ G $ is triangle-free, then $ \chi(G,p)\leq\frac{7}{6}\omega(G,p) + 5 $ (See also [SV]). The conjecture would be implied by the following one, where $ \mathbf{4} $ is the all $ 4 $ function. Conjecture $ \chi(G,\mathbf{4})\leq 9 $ for every hexagonal graph. Since $ \chi(G,\mathbf{4}) \geq 4|V(G)|/\alpha(G) $ , where $ \alpha(G) $ is the stability number (the maximum size of a stable set). A first step to this later conjecture would be to prove the following conjecture of McDiarmid. Conjecture Let $ G $ be a triangle-free hexagonal graph. $$\alpha(G)\geq \frac{4}{9}|V(G)|$$