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 | KRÁĽ, Daniel a R SKEKOVSKI. Borodin's conjecture on diagonal coloring is false. European Journal of Combinatorics. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2004, roč. 25, č. 6, s. 813-816. ISSN 0195-6698. Dostupné z: https://dx.doi.org/10.1016/j.ejc.2003.04.004. |
| 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. |