Informace o publikaci
Borodin's conjecture on diagonal coloring is false
| Autoři | |
|---|---|
| Rok publikování | 2004 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | European Journal of Combinatorics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2003.04.004 |
| Popis | 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. |