Mathematics – Combinatorics
Scientific paper
2009-01-17
Mathematics
Combinatorics
18 pages, 9 figures
Scientific paper
The chromatic number of an planar graph is not greater than four and this is known by the famous four color theorem and is equal to two when the planar graph is bipartite. When the planar graph is even-triangulated or all cycles are greater than three we know by the Heawood and the Grotszch theorems that the chromatic number is three. There are many conjectures and partial results on three colorability of planar graphs when the graph has specific cycles lengths or cycles with three edges (triangles) have special distance distributions. In this paper we have given a new three colorability criteria for planar graphs that can be considered as an generalization of the Heawood and the Grotszch theorems with respect to the triangulation and cycles of length greater than 3. We have shown that an triangulated planar graph with disjoint holes is 3-colorable if and only if every hole satisfies the parity symmetric property, where a hole is a cycle (face boundary) of length greater than 3.
No associations
LandOfFree
On the Three Colorability of Planar Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Three Colorability of Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Three Colorability of Planar Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-118989