Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable (Q1026007)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5569118
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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.9705288
0 references
0.96432436
0 references
0.9591525
0 references
0.95807076
0 references
0.9541404
0 references
0.95040166
0 references
0.94136125
0 references
0.9413044
0 references
