|
|
A328061
|
|
Number of 4-chromatic Laman graphs on n vertices.
|
|
2
|
|
|
|
OFFSET
|
7,2
|
|
COMMENTS
|
All the Laman graphs (in other words, minimally rigid graphs) can be constructed by the inductive Henneberg construction, i.e., a sequence of Henneberg steps starting from K_2. A new vertex added by a Henneberg move is connected with two or three of the previously existing vertices. Hence, the chromatic number of a Laman graph can be 2, 3 or 4. One can hypothesize that the set of 3-chromatic Laman graphs is the largest and that bipartite graphs are relatively rare. The simplest example of a 4-chromatic Laman graph is the Moser spindle.
|
|
LINKS
|
Christoph Koutschan, Mathematica program for generating a list of non-isomorphic Laman graphs on n vertices.
Eric Weisstein's World of Mathematics, Moser spindle is a 4-chromatic Laman graph.
|
|
MATHEMATICA
|
Table[Length[
Select[LamanGraphs[n],
IGChromaticNumber[AdjacencyGraph[G2Mat[#]]] == 4 &]], {n, 7, 9}]
(* using the program by Christoph Koutschan for generating Laman graphs, see A227117, and IGraph/M interface by Szabolcs Horvát *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|