Publication details
Borodin's conjecture on diagonal coloring is false
| Authors | |
|---|---|
| Year of publication | 2004 |
| Type | Article in Periodical |
| Magazine / Source | European Journal of Combinatorics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2003.04.004 |
| Description | In a 1-diagonal coloring, vertices of any face and vertices of any two faces sharing an edge have to get different colors. Borodin proved that any triangulation of a surface of Euler gerus g greater than or equal to I can be 1-diagonally colored by [13+root73+48g/2] colors. The bound is conjectured to be sharp for all surfaces except for the sphere (g = 0). We disprove this conjecture. (C) 2004 Elsevier Ltd. All rights reserved. |