|
| The 3-coloring of planar graphs withadjacent triangles |
| Zuosong Liang,Xin Xue |
| (School of Mathematics, Guangxi Minzu University, Nanning 530006, China) |
| DOI： |
| Abstract: |
| Erd?os raised the following problem according to Steinberg’s conjecture: Is there an integer such that every planar graph without cycles of length
from 4 to k is 3-colorable. By far, the result about the problem was improved
to k ≤ 7 by Borodin et al. However, by permitting the existence of adjacent
triangles except K4, for an arbitrary integer k ≥5, there exists a planar graph
without cycles of length from 5 to k such that G is not 3-colorable. Let d denote
the minimum distance between two diamonds in G, where a diamond is the
union of two adjacent triangles. In this paper, we prove that a planar graph G
with d≥2 and without cycles of length from 5 to 18 is 3-colorable. The reader
is invited to find the smallest integer k such that a planar graph G with d≥2
and without cycles of length from 5 to k is 3-colorable. |
| Key words: Three Color Problem; adjacent triangles; cycle; planar graph. |