A350361 2-tone chromatic number of a tree with maximum degree n.

4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15

Offset

1,1

Comments

The 2-tone chromatic number of a graph G is the smallest number of colors for which G has a coloring where every vertex has two distinct colors, no adjacent vertices have a common color, and no pair of vertices at distance 2 have two common colors.

a(n) is also the 2-tone chromatic number of a star with n leaves.

Links

Table of n, a(n) for n=1..71.

A. Bickle and B. Phillips, t-Tone Colorings of Graphs, Utilitas Math, 106 (2018) 85-102.

Allan Bickle, 2-Tone coloring of joins and products of graphs, Congr. Numer. 217 (2013), 171-190.

N. Fonger, J. Goss, B. Phillips, and C. Segroves, Math 6450: Final Report, (2009).

Formula

a(n) = A003057(n-1) + 2.

a(n) = ceiling((5 + sqrt(1 + 8*n))/2).

Example

For a star with three leaves, label the leaves 12, 13, and 23.  Label the other vertex 45.  A total of 5 colors are used, so a(3)=5.

Mathematica

Table[Ceiling[(5 + Sqrt[1 + 8*n])/2], {n, 71}] (* Stefano Spezia, Dec 27 2021 *)

Crossrefs

Cf. A003057, A350362.

Sequence in context: A021691 A248926 A107575 * A376167 A205677 A178400

Adjacent sequences: A350358 A350359 A350360 * A350362 A350363 A350364

Keyword

nonn,easy

Author

Allan Bickle, Dec 26 2021

Status

approved