The Moore four-color graph is a 341-vertex planar graph due to E. F. Moore that is somewhat resistant to graph coloring with four colors by hand (Wagon 1999). It has 1017 edges and chromatic number 4.
The Moore four-color graph should not be confused with the much more common use of the term Moore graph in the sense of a regular graph that is a cage graph.
The Moore four-color partial graph is a 341-vertex spanning subgraph of the Moore four-color graph obtained by deleting 31 edges. It is also planar and has chromatic number 4, but is easier to draw while still providing a useful test case for graph coloring with four colors.
The Moore four-color graph and Moore four-color partial graph will be implemented in a future version of the Wolfram Language as GraphData["MooreFourColorGraph"] and GraphData["MooreFourColorPartialGraph"], respectively.
