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

From MaRDI portal





scientific article; zbMATH DE number 5569118
Language Label Description Also known as
English
Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
scientific article; zbMATH DE number 5569118

    Statements

    Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable (English)
    0 references
    23 June 2009
    0 references
    \textit{0. V. Borodin}, \textit{A. N. Glebvov}, \textit{A. Raspaud} and \textit{M. R. Salavatipour} [J. Comb. Theory, Ser. B 93, No. 2, 303--311 (2005; Zbl 1056.05052)] showed that planar graphs without cycles of length 4, 5, 6, or 7 are 3-colorable. The present authors improve this result by proving that planar graphs without cycles of length 5 or 7 and also without adjacent triangles are 3-colorable. They also give counterexamples to the argument given for the same result by \textit{B. Xu} [J. Comb. Theory, Ser. B 96, No. 6, 958--963 (2006; Zbl 1108.05046)].
    0 references
    planar graphs
    0 references
    coloring
    0 references
    three color problem
    0 references
    Steinberg's conjecture
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers