Record Details

A technique for multicoloring triangle-free hexagonal graphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A technique for multicoloring triangle-free hexagonal graphs
 
Creator SUDEEP, KS
VISHWANATHAN, S
 
Subject hexagonal graphs
multicoloring triangular lattice
triangle-free
 
Description In order to avoid interference in cellular telephone networks, sets of radio frequencies are to be assigned to transmitters such that adjacent transmitters are allotted disjoint sets of frequencies. Often these transmitters are laid out like vertices of a triangular lattice in a plane. This problem corresponds to the problem of multicoloring an induced subgraph of a triangular lattice with integer demands associated with each vertex. We deal with the simpler case of triangle-free subgraphs of the lattice. [Frederic Havet, Discrete Math. 233 (2001) 1-3] uses inductive arguments to prove that triangle-free hexagonal graphs can be colored with 7/6w(d) + o(1) colors where omega(d) is the maximum demand on a clique in the graph. We give a simpler proof and hope that our techniques can be used to prove the conjecture by [McDiarmid and Reed, Networks Suppl. 36 (2000) 114-117] that these graphs are 9/8 omega(d) + o(l)-multicolorable. (c) 2005
 
Publisher ELSEVIER SCIENCE BV
 
Date 2011-07-22T20:46:35Z
2011-12-26T12:52:34Z
2011-12-27T05:38:48Z
2011-07-22T20:46:35Z
2011-12-26T12:52:34Z
2011-12-27T05:38:48Z
2005
 
Type Article
 
Identifier DISCRETE MATHEMATICS, 300(1-3), 256-259
0012-365X
http://dx.doi.org/10.1016/j.disc.2005.06.002
http://dspace.library.iitb.ac.in/xmlui/handle/10054/6353
http://hdl.handle.net/10054/6353
 
Language en