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.