A121816 Conjectured chromatic number of the square of an outerplanar graph G^2 as a function of the maximum degree of a vertex of G.

9, 10, 11, 12, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88, 89, 91, 92, 94, 95, 97, 98, 100

Offset

4,1

Links

Table of n, a(n) for n=4..66.

Ko-Wei Lih and Wei-Fan Wang, Coloring the Square of an Outerplanar Graph, Taiwanese Journal of Mathematics, Vol. 10, No. 4, 2006, pp. 1015-1023.

Michael Molloya and Mohammad R.Salavatipour, A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B 94 (2005) 189-213.

G. Wegner, Graphs with given diameter and a coloring problem, University of Dortmund, 1977 [cited by Lih and Wang as source of conjecture].

Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Formula

a(n) = n + 5 if 4 <= n <= 7; a(n) = floor(3*n/2) + 1 if n >= 8.

a(n) = (3+(-1)^n+6*n)/4 for n>7. a(n) = a(n-1)+a(n-2)-a(n-3). G.f.: x^4*(x^6-8*x^2+x+9) / ((x-1)^2*(x+1)). - Colin Barker, Apr 30 2013

Crossrefs

Sequence in context: A115843 A058365 A162789 * A196105 A196108 A181699

Adjacent sequences: A121813 A121814 A121815 * A121817 A121818 A121819

Keyword

nonn,easy

Author

Jonathan Vos Post, Aug 26 2006

Status

approved