Importance: Medium ✭✭
 Author(s): McDiarmid, Colin Reed, Bruce A.
 Subject: Graph Theory » Coloring » » Vertex coloring
 Keywords:
 Recomm. for undergrads: no
 Posted by: fhavet on: March 13th, 2013
Conjecture   There is an absolute constant such that for every hexagonal graph and vertex weighting , 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.

Conjecture for every hexagonal graph.

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.

Conjecture   Let be a triangle-free hexagonal graph. ## 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.