Accession Number:

AD0614412

Title:

FOUR-COLOR REDUCIBILITY OF PLANAR GRAPHS CONTAINING SUBGRAPHS WITH FOUR- POINT BOUNDARIES

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1965-04-01

Pagination or Media Count:

5.0

Abstract:

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.

Subject Categories:

  • Printing and Graphic Arts

Distribution Statement:

APPROVED FOR PUBLIC RELEASE