Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Mathematics
Coloring The Square Of Planar Graphs Without 4-Cycles Or 5-Cycles, Robert Jaeger
Coloring The Square Of Planar Graphs Without 4-Cycles Or 5-Cycles, Robert Jaeger
Theses and Dissertations
The famous Four Color Theorem states that any planar graph can be properly colored using at most four colors. However, if we want to properly color the square of a planar graph (or alternatively, color the graph using distinct colors on vertices at distance up to two from each other), we will always require at least \Delta + 1 colors, where \Delta is the maximum degree in the graph. For all \Delta, Wegner constructed planar graphs (even without 3-cycles) that require about \frac{3}{2} \Delta colors for such a coloring.
To prove a stronger upper bound, we consider only planar graphs …