Borodin's conjecture on diagonal coloring is false

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://doi.org/10.1016/j.ejc.2003.04.004.

Základní údaje

Originální název

Borodin's conjecture on diagonal coloring is false

Autoři

KRÁĽ, Daniel a R SKEKOVSKI

Vydání

European Journal of Combinatorics, LONDON, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2004, 0195-6698

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.303

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.ejc.2003.04.004

UT WoS

000223480400006

---

Anotace

V originále

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.