zbMATH — the first resource for mathematics

A new type of 4-colour reducibility. (English) Zbl 0764.05026
Combinatorics, graph theory, and computing, Proc. 22nd Southeast Conf., Baton Rouge/LA (USA) 1991, Congr. Numerantium 82, 33-48 (1991).
Summary: [For the entire collection see Zbl 0747.00033.]
The reducible configurations used in the proof of the 4-colour theorem have heretofore been determined by means of a form of Boolean closure of the set of colourings for these configurations. It has long been known that it is possible to achieve a stronger form of closure by making use of linear rather than Boolean constraints. It is thus conceivable that configurations, which are irreducible within the framework of Boolean closure, might nevertheless be reducible within the linear framework. This paper sets out in detail an example of this phenomenon in the case of the configuration 7[5665], which is the first example of a reducible configuration whose reducibility is inaccessible within the traditional framework.

05C15 Coloring of graphs and hypergraphs
05B30 Other designs, configurations