The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A221222 Threshold for the P(n)-avoidance vertex-coloring game with two colors and fixed tree size restriction, where P(n) denotes the path on n vertices (see the comments and reference for precise definition). 1
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 791, 841, 902, 961, 1040, 1089, 1156, 1225, 1323, 1376, 1449, 1521, 1641, 1699, 1796, 1856, 1991, 2057, 2160, 2225, 2378, 2447, 2563, 2633, 2795, 2873 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
The game is played on a vertex-colored graph by two players called Builder and Painter. The game starts with an empty graph, i.e., no vertices are present in the beginning. In each step, Builder adds one new vertex to the graph, and a number of edges leading from previous vertices to this new vertex. Builder must not create any cycles, and all components (=trees) may have at most k vertices (k is fixed throughout the game). Painter immediately and irrevocably colors each new vertex red or blue. Painter's goal is to avoid creating a monochromatic (i.e., completely red or completely blue) path P(n) on n vertices (n is also fixed throughout the game). Builder's goal is to force Painter to create such a monochromatic P(n). a(n) is defined as the minimal k for which Builder wins this P(n)-avoidance game with two colors and tree size restriction k.
a(n)=n^2 exactly for all n in the set {1,...,27} U {29,31,33,34,35,39}, and a(n)>n^2 otherwise.
There are constants c_1 and c_2 such that c_1*n^2.01 <= a(n) <= c_2*n^2.59.
LINKS
T. Mütze and R. Spöhel, On the path-avoidance vertex-coloring game, Electronic Journal of Combinatorics, 18(1) (2011), Research Paper 163, 33 pages.
EXAMPLE
For n=28, we have a(28)=791=28^2+7, meaning that the P(28)-avoidance game with two colors and tree size restriction k is a win for Builder for all k>=791, and a win for Painter for all k<791.
CROSSREFS
Sequence in context: A162395 A253909 A305559 * A144913 A018885 A025741
KEYWORD
nonn,hard
AUTHOR
Torsten Muetze, Feb 22 2013
EXTENSIONS
a(51)-a(53) from Torsten Muetze, Apr 22 2014
STATUS
approved

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 23 05:11 EDT 2024. Contains 372758 sequences. (Running on oeis4.)