|
Search: id:A121816
|
|
|
| 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
1
|
|
| 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; listen)
|
|
|
OFFSET
|
4,1
|
|
|
COMMENT
|
Best known upper bound is 5*n/3 + 78, established by Molloy and Salavatipour.
|
|
REFERENCES
|
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
G. Wegner, Graphs with given diameter and a coloring problem, preprint, University of Dortmund, 1977 [cited by Lih and Wang as source of conjecture].
|
|
FORMULA
|
a(n) = n + 5 if 4 <= n <= 7; floor[3*n/2] + 1 if n => 8.
|
|
CROSSREFS
|
Sequence in context: A115843 A058365 A162789 this_sequence A001731 A129849 A097480
Adjacent sequences: A121813 A121814 A121815 this_sequence A121817 A121818 A121819
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 26 2006
|
|
|
Search completed in 0.002 seconds
|
