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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1965
Accession Number
AD0614412

Entities

People

  • Norman C. Dalkey

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Boundaries
  • Corporations
  • Hard Copy
  • Microfiche
  • Photographic Materials
  • Photography
  • Triangles

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Organizational Psychology.