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

Author

Allan Bickle, Dec 26 2021

Keywords

• nonn
• easy

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.

Examples

			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.
		

Links

• 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).

Crossrefs

Cf. A003057, A350362.

Programs

Mathematica

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

Formula

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

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