Graphs with bounded tree-width and large odd-girth are almost bipartite
| Autor: | Daniel Král, Jean-Sébastien Sereni, Alexandr V. Kostochka, Michael Stiebitz |
|---|---|
| Přispěvatelé: | Department of Mathematics [Urbana], University of Illinois at Urbana-Champaign [Urbana], University of Illinois System-University of Illinois System, Institute of Mathematics [Novosibirsk], Institute of Mathematics of Novosibirsk, Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institute of Mathematics - Technical University of Ilmenau, Ilmenau University of Technology [Germany] (TU) |
| Rok vydání: | 2010 |
| Předmět: |
Odd-girth
Circular coloring Tree-width 0102 computer and information sciences [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Theoretical Computer Science Combinatorics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Chromatic scale 05C83 0101 mathematics Mathematics Discrete mathematics 010102 general mathematics 05C15 Graph Treewidth Computational Theory and Mathematics 010201 computation theory & mathematics Bounded function Bipartite graph Combinatorics (math.CO) |
| Zdroj: | Journal of Combinatorial Theory, Series B Journal of Combinatorial Theory, Series B, Elsevier, 2010, 100 (6), pp.554--559. ⟨10.1016/j.jctb.2010.04.004⟩ |
| ISSN: | 0095-8956 1096-0902 |
| DOI: | 10.1016/j.jctb.2010.04.004 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect