
Weighted colouring of hexagonal graphs.




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.

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.


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.