

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.


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

4,1


COMMENTS

Best known upper bound is 5*n/3 + 78, established by Molloy and Salavatipour.


REFERENCES

KoWei Lih and WeiFan Wang, Coloring the Square of an Outerplanar Graph, Taiwanese Journal of Mathematics, Vol. 10, No. 4, 2006, pp. 10151023
G. Wegner, Graphs with given diameter and a coloring problem, preprint, University of Dortmund, 1977 [cited by Lih and Wang as source of conjecture].


LINKS

Table of n, a(n) for n=4..66.
Index entries for linear recurrences with constant coefficients, signature (1,1,1).


FORMULA

a(n) = n + 5 if 4 <= n <= 7; floor[3*n/2] + 1 if n => 8.
a(n) = (3+(1)^n+6*n)/4 for n>7. a(n) = a(n1)+a(n2)a(n3). G.f.: x^4*(x^68*x^2+x+9) / ((x1)^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



