FOUR-COLOR REDUCIBILITY OF PLANAR GRAPHS CONTAINING SUBGRAPHS WITH FOUR- POINT BOUNDARIES
RAND CORP SANTA MONICA CA
Pagination or Media Count:
An inductive hypothesis is offered concerning the 4-color reducibility within a planar graph where the boundary between a proper subgraph and its complement has 4 points. Where such a graph having a boundary with 4 points is fully triangulated, the boundary points will form a square the two components can be completed by connecting opposite corners of the square, and the opposite corners must be assigned different colors. The inductive hypothesis shows that 1 graphs smaller than the original graph can be 4-colored, 2 each of the components will have several possible colorings, and 3 there will always be a pair of colorings for the components that will match.
- Printing and Graphic Arts