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
L. Henneberg, Die graphische Statik der starren Systeme, Leipzig, 1911.
Christoph Koutschan, Mathematica program for generating a list of non-isomorphic Laman graphs on n vertices.
G. Laman, On Graphs and Rigidity of Plane Skeletal Structures, J. Engineering Mathematics, Vol. 4, No. 4, 1970, pp. 331-340; alternative link.
Martin Larsson, Nauty Laman plugin
A. Nixon, E. Ross, One brick at a time: a survey of inductive constructions in rigidity theory, arXiv:1203.6623 [math.MG], 2012-2013.
Vsevolod Voronov, Anna Neopryatnaya, and Eugene Dergachev, Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres, arXiv:2106.11824 [math.CO], 2021.
Eric Weisstein's World of Mathematics, Moser spindle is a 4-chromatic Laman graph.
Wikipedia, 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 *)
PROG
(nauty with Laman plugin) gensparseg $n -K2 | countg --N # see link
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Vsevolod Voronov, Oct 03 2019
EXTENSIONS
a(13)-a(15) added by Georg Grasegger, Sep 09 2024
STATUS
approved