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 that contain no 4-cycles and no 5-cycles (but which may contain 3-cycles). Zhu, Lu, Wang, and Chen showed that for a graph G in this class with \Delta \ge 9, we can color G^2 using no more than \Delta + 5 colors. In this thesis we improve this result, showing that for a planar graph G with maximum degree \Delta \ge 32 having no 4-cycles and no 5-cycles, at most \Delta + 3 colors are needed to properly color G^2. Our approach uses the discharging method, and the result extends to list-coloring and other related coloring concepts as well.

In this thesis, we consider packings and coverings of various complete graphs with the 4-cycle with a pendant edge. We consider both restricted and unrestricted coverings. Necessary and sufficient conditions are given for such structures for (1) complete graphs Kv, (2) complete bipartite graphs Km,n, and (3) complete graphs with a hole K(v,w).