OFFSET
1,8
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 first nontrivial bipartite Laman graph is K_{3,3}. An infinite sequence of such graphs can be obtained from K_{3,3} by Henneberg moves of the first type (i.e., adding a vertex and connecting it with two of the existing vertices from the one part).
LINKS
L. Henneberg, Die graphische Statik der starren Systeme, Leipzig, 1911.
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties.
Christoph Koutschan, Mathematica program for generating a list of non-isomorphic Laman graphs on n vertices.
G. Laman, On Graphs and Rigidity of Planar Skeletal Structures, J. Engineering Mathematics, Vol. 4, No. 4, 1970, pp. 331-340.
Martin Larsson, C program
A. Nixon and E. Ross, One brick at a time: a survey of inductive constructions in rigidity theory, arXiv:1203.6623 [math.MG], 2012-2013.
Wikipedia, Laman graph
MATHEMATICA
Table[Length[
Select[LamanGraphs[n],
BipartiteGraphQ[AdjacencyGraph[G2Mat[#]]] &]], {n, 6, 9}] (* using the program by Christoph Koutschan for generating Laman graphs, see A227117 *)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Vsevolod Voronov, Oct 03 2019
EXTENSIONS
a(13)-a(15) added using tinygraph by Falk Hüffner, Oct 20 2019
a(16)-a(17) added by Martin Larsson, Dec 21 2020
STATUS
approved