Article ID Journal Published Year Pages File Type
421453 Discrete Applied Mathematics 2007 5 Pages PDF
Abstract

In this paper, a structural theorem about toroidal graphs is given that strengthens a result of Borodin on plane graphs. As a consequence, it is proved that every toroidal graph without adjacent triangles is (4,1)*(4,1)*-choosable. This result is best possible in the sense that K7K7 is a non-(3,1)*(3,1)*-choosable toroidal graph. A linear time algorithm for producing such a coloring is presented also.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,