The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328061 Number of 4-chromatic Laman graphs on n vertices. 1
1, 8, 102, 1601, 29811, 636686 (list; graph; refs; listen; history; text; internal format)



All the Laman graphs (in other terms, 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.


Table of n, a(n) for n=7..12.

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.

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




   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 *)


Cf. A227117, A273468, A328060.

Sequence in context: A307461 A318213 A001575 * A305603 A333985 A297069

Adjacent sequences:  A328058 A328059 A328060 * A328062 A328063 A328064




Vsevolod Voronov, Oct 03 2019



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 25 03:39 EDT 2022. Contains 354047 sequences. (Running on oeis4.)