• Title of article

    Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable

  • Author/Authors

    Borodin، نويسنده , , O.V. and Glebov، نويسنده , , A.N. and Montassier، نويسنده , , M. and Raspaud، نويسنده , , A.، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2009
  • Pages
    6
  • From page
    668
  • To page
    673
  • Abstract
    It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable [O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B 93 (2005) 303–311]. We improve this result by proving that every planar graph without 5- and 7-cycles and without adjacent triangles is 3-colorable. Also, we give counterexamples to the proof of the same result in [B. Xu, On 3-colorable plane graphs without 5- and 7-cycles, J. Combin. Theory Ser. B 96 (2006) 958–963].
  • Keywords
    Steinbergיs conjecture , Coloring , Three Color Problem , Planar graphs
  • Journal title
    Journal of Combinatorial Theory Series B
  • Serial Year
    2009
  • Journal title
    Journal of Combinatorial Theory Series B
  • Record number

    1528861