Graphs with bounded tree-width and large odd-girth are almost bipartite

KOSTOCHKA, AV; Daniel KRÁĽ; JS SERENI a M STIEBITZ. Graphs with bounded tree-width and large odd-girth are almost bipartite. JOURNAL OF COMBINATORIAL THEORY SERIES B. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2010, roč. 100, č. 6, s. 554-559. ISSN 0095-8956. Dostupné z: https://doi.org/10.1016/j.jctb.2010.04.004.

Základní údaje

Originální název

Graphs with bounded tree-width and large odd-girth are almost bipartite

Autoři

KOSTOCHKA, AV; Daniel KRÁĽ; JS SERENI a M STIEBITZ

Vydání

JOURNAL OF COMBINATORIAL THEORY SERIES B, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2010, 0095-8956

---

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: 1.043

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.jctb.2010.04.004

UT WoS

000281907600004

Klíčová slova anglicky

Circular coloring; Odd-girth; Tree-width

---

Anotace

V originále

We prove that for every k and every epsilon > 0, there exists g such that every graph with tree-width at most k and odd-girth at least g has circular chromatic number at most 2 + epsilon. (C) 2010 Elsevier Inc. All rights reserved.