Search Results for ""

The Poussin graph is the 15-node planar graph illustrated above that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof ...

Let G be a planar graph whose vertices have been properly colored and suppose v in V(G) is colored C_1. Define the C_1C_2-Kempe chain containing v to be the maximal connected ...

An algorithm which can be used to find a good, but not necessarily minimal, edge or vertex coloring for a graph. However, the algorithm does minimally color complete ...

A k-coloring of a graph G is a vertex coloring that is an assignment of one of k possible colors to each vertex of G (i.e., a vertex coloring) such that no two adjacent ...

The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color (Skiena 1990, p. ...

Rule 30 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its ...

The chromatic polynomial pi_G(z) of an undirected graph G, also denoted C(G;z) (Biggs 1973, p. 106) and P(G,x) (Godsil and Royle 2001, p. 358), is a polynomial which encodes ...

The Kittell graph is a planar graph on 23 nodes and 63 edges that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of ...

A Turing machine is a theoretical computing machine invented by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine consists of a ...

Let N^* be the smallest dimension n of a hypercube such that if the lines joining all pairs of corners are two-colored for any n>=N^*, a complete graph K_4 of one color with ...