On the Three Colorability of Planar Graphs - Mathematics > CombinatoricsReport as inadecuate

On the Three Colorability of Planar Graphs - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: The chromatic number of an planar graph is not greater than four and this isknown by the famous four color theorem and is equal to two when the planargraph is bipartite. When the planar graph is even-triangulated or all cyclesare greater than three we know by the Heawood and the Grotszch theorems thatthe chromatic number is three. There are many conjectures and partial resultson three colorability of planar graphs when the graph has specific cycleslengths or cycles with three edges triangles have special distancedistributions. In this paper we have given a new three colorability criteriafor planar graphs that can be considered as an generalization of the Heawoodand the Grotszch theorems with respect to the triangulation and cycles oflength greater than 3. We have shown that an triangulated planar graph withdisjoint holes is 3-colorable if and only if every hole satisfies the paritysymmetric property, where a hole is a cycle face boundary of length greaterthan 3.

Author: I. Cahit

Source: https://arxiv.org/


Related documents