The Catlin graph is the graph lexicographic product ![C_5[K_3]](/images/equations/CatlinGraph/Inline1.svg)
of the cycle graph 
and the complete graph 
, shown above in a graph drawing due
to Bondy and Murty (2008, Fig. 14.3, p. 364). It is constructed by replacing
each graph vertex of 
with a triangle graph
and joining every graph vertex in one triangle
graph to every graph vertex in each neighboring
triangle graph.
It has 15 vertices and 60 edges, and is an octic graph. It is isomorphic to the circulant graph 
.
The chromatic number of the Catlin graph is 8. Each independent vertex set contains at
most two vertices, so at least eight colors are needed.
An eight-color vertex coloring is obtained by
assigning the color sets 
, 
, 
, 
, and 
to the five triangle graphs
in cyclic order.
The Catlin graph contains no graph subdivision of the complete graph 
, making it a counterexample
to the Hajós conjecture (Catlin 1979;
Bondy and Murty 2008, p. 410). To see this, any eight proposed branch vertices
must occupy two nonneighboring triangle graphs,
since two neighboring triangle graphs contain only
six vertices. Removing the six vertices
in the two triangle graphs neighboring one of those
triangle graphs separates a pair of proposed branch
vertices. However, any two branch vertices
of a graph subdivision of 
are joined by seven internally vertex-disjoint paths.
The six-vertex vertex cut
therefore rules out such a graph subdivision.
