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

Alexandr V. Kostochka, Daniel Král', Jean Sébastien Sereni, Michael Stiebitz

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that for every k and every ε>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+ε.

Original languageEnglish (US)
Pages (from-to)554-559
Number of pages6
JournalJournal of Combinatorial Theory. Series B
Volume100
Issue number6
DOIs
StatePublished - Nov 2010

Keywords

  • Circular coloring
  • Odd-girth
  • Tree-width

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Graphs with bounded tree-width and large odd-girth are almost bipartite'. Together they form a unique fingerprint.

Cite this