OFFSET
0,1
COMMENTS
Gravin's abstract: Let c => 2 and p => c be two integers. We will call a proper coloring of the graph G a (c,p)-nondegenerate, if for any vertex of G with degree at least p there are at least c vertices of different colors adjacent to it. In our work we prove the following result, which generalizes Brook's Theorem. Let D => 3 and G be a graph without cliques on D+1 vertices and the degree of any vertex in this graph is not greater than D. Then for every integer c => 2 there is a proper (c,p)-nondegenerate vertex D-coloring of G, where p=(c^3+8c^2+19c+6)(c+1). During the primary proof, some interesting corollaries are derived.
LINKS
Nikolay Gravin, Non-degenerate colorings in the Brook's Theorem, Dec 1, 2008.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).
FORMULA
a(n) = (n^3+8*n^2+19*n+6)*(n+1).
G.f.: 2(3+19x-14x^2+4x^3)/(1-x)^5. [From R. J. Mathar, Dec 04 2008]
EXAMPLE
a(2) = 252 because ((2^3) + (8 * (2^2)) + (19 * 2) + 6) * (2 + 1) = 252.
MATHEMATICA
LinearRecurrence[{5, -10, 10, -5, 1}, {6, 68, 252, 648, 1370}, 50] (* Harvey P. Dale, Jan 29 2023 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Jonathan Vos Post, Dec 03 2008
STATUS
approved