![](/files/happy5.png)
![$ c $](/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ p:V(G)\rightarrow \mathbb{N} $](/files/tex/6b14cbdc1cda96520fd87d9507b262f943ccf8ba.png)
![$$\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c $$](/files/tex/9b4ccf7620c2a90a97c40177afd9201723864ba8.png)
A hexagonal graph is an induced subgraph of the triangular lattice. The triangular lattice may be described as follows. The vertices are all integer linear combinations
of the two vectors
and
. Two vertices are adjacent when the Euclidean distance between them is 1.
Let be a graph and
a vertex weighting
. The weighted clique number of
, denoted by
, is the maximum weight of a clique, that is
, where
. A
-colouring of a
is a mapping
such that for every vertex
,
and for all edge
,
. The chromatic number of
, denoted by
, is the least integer
such that
admits a
-colouring.
The conjecture would be tight because of the cycle of length 9. The maximum size of stable set in
is
. Thus
and
, where
is the all
function.
McDiarmid and Reed [MR] proved that for any hexagonal graph
and vertex weighting
. Havet [H] proved that if a hexagonal graph
is triangle-free, then
(See also [SV]).
The conjecture would be implied by the following one, where is the all
function.
![$ \chi(G,\mathbf{4})\leq 9 $](/files/tex/936e87839ae7c64854cc21089836e69c898e165f.png)
Since , where
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.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$$\alpha(G)\geq \frac{4}{9}|V(G)|$$](/files/tex/081f51f1078b3e87e3748f42649529378aefb8c2.png)
Bibliography
[H] F.Havet. Channel assignment and multicolouring of the induced subgraphs of the triangular lattice. Discrete Mathematics 233:219--231, 2001.
*[MR] C. McDiarmid and B. Reed. Channel assignment and weighted coloring, Networks, 36:114--117, 2000.
[SV] K. S. Sudeep and S. Vishwanathan. A technique for multicoloring triangle-free hexagonal graphs. Discrete Mathematics, 300(1-3), 256--259, 2005.
* indicates original appearance(s) of problem.