Booth Id:
MATH024
Category:
Mathematics
Year:
2017
Finalist Names:
Lin, Juei-Yin (School: Rockdale Magnet School for Science and Technology)
Abstract:
Appel and Haken (1977) proved that four colors suffice to color any map by using the discharging method. While the original problem required the same four colors, but what if each country has its own four colors to choose from. Can the map still be colored properly via this way of list coloring? This problem is NP-hard according to Gutner.
This challenging problem can be studied through vertex coloring. Previously, Thomassen proved that every planar graph is 5-list colorable. Lam et al. later demonstrated that a planar graph without 4-cycles is 4-list colorable. These and other studies identified sufficient conditions for 4-list colorability by constraining on the existence of 3-cycles, 4-cycles etc. and on the adjacency of short cycles. Their best results require a distance of at least one between short cycles. We asked if this condition can be improved to requiring just nonnegative distance.
We used the idea of nonnegative distance to construct various graphs, and eventually identified a sufficient condition for planar graphs to be 4-list colorable if they contain no adjacent 3-cycles, adjacent 4-cycles and suns. Then we used proof by contradiction to establish its validity. We first assumed that the claim was false and that there existed a minimal counterexample, say graph G, the properties of which could be identified. We then applied the discharging method to prove that this counterexample could not exist under our three conditions. Specifically, we designed several discharging rules and assigned suitable charges to the vertices and faces of G while requiring that the total charge should remain unchanged. Should the minimal counterexample exist, we proved that its subsequent total charge would be different from the initial one, thereby resulting in a contradiction.
Awards Won:
Third Award of $1,000