Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421453 | Discrete Applied Mathematics | 2007 | 5 Pages |
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
Baogang Xu, Haihui Zhang,