• DocumentCode
    579978
  • Title

    Combinatorial Coloring of 3-Colorable Graphs

  • Author

    Kawarabayashi, Ken-ichi ; Thorup, Mikkel

  • Author_Institution
    Nat. Inst. of Inf., Tokyo, Japan
  • fYear
    2012
  • fDate
    20-23 Oct. 2012
  • Firstpage
    68
  • Lastpage
    75
  • Abstract
    We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We present a combinatorial algorithm getting down to Õ(n4/11) colors. This is the first combinatorial improvement of Blum´s Õ(n3/8) bound from FOCS´90. Like Blum´s algorithm, our new algorithm composes nicely with recent semi-definite programming approaches. The current best bound is Õ(n0.2072) colors by Chlamtac from FOCS´07. We now bring it down to Õ(n0. 2049) colors.
  • Keywords
    computational complexity; graph colouring; mathematical programming; 3-colorable graph; Õ(n0.2072) colors; Õ(n0. 2049) colors; Õ(n4/11) colors; combinatorial coloring algorithm; polynomial time; semi-definite programming approaches; Algorithm design and analysis; Approximation algorithms; Approximation methods; Color; Computer science; Electronic mail; Polynomials; Approximation Algorithms; Graph Coloring;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on
  • Conference_Location
    New Brunswick, NJ
  • ISSN
    0272-5428
  • Print_ISBN
    978-1-4673-4383-1
  • Type

    conf

  • DOI
    10.1109/FOCS.2012.16
  • Filename
    6375283
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=579978