Home » Subject » Graph Theory » Coloring » Vertex coloring
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 $ c $ such that for every hexagonal graph $ G $ and vertex weighting $ p:V(G)\rightarrow \mathbb{N} $, $$\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c $$

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)|$$

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.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options