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, SUNDAR
 
Subject mathematical models
problem solving
set theory
transmitters
 
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. [Frédéric Havet, Discrete Math. 233 (2001) 1–3] uses inductive arguments to prove that triangle-free hexagonal graphs can be colored with 7/6 wd + o(1) colors where ω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 wd + o(1)-multicolorable.
 
Publisher Elsevier
 
Date 2009-05-10T09:06:34Z
2011-12-08T07:07:04Z
2011-12-26T13:01:58Z
2011-12-27T05:47:47Z
2009-05-10T09:06:34Z
2011-12-08T07:07:04Z
2011-12-26T13:01:58Z
2011-12-27T05:47:47Z
2007
 
Type Article
 
Identifier Discrete Mathematics 300(1-3), 256-2596
0012-365X
10.1016/j.disc.2005.06.002
http://hdl.handle.net/10054/1336
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1336
 
Language en