A366727 2-tone chromatic number of a maximal outerplanar graph with maximum degree n.

4, 6, 7, 7, 7, 7, 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, 15, 15

Offset: 1

Author

Allan Bickle, Oct 17 2023

Keywords

• nonn

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 fan with n+1 vertices.

Examples

			The fan with 11 vertices has a path colored 12-34-15-23-45-13-24-35-14-25 joined to a vertex colored 67, so a(10) = 7.
		

Links

• Allan Bickle, 2-Tone coloring of joins and products of graphs, Congr. Numer. 217 (2013), 171-190.
• Allan Bickle, 2-Tone Coloring of Chordal and Outerplanar Graphs, Australas. J. Combin. 87 1 (2023) 182-197.
• Allan Bickle and B. Phillips, t-Tone Colorings of Graphs, Utilitas Math, 106 (2018) 85-102.
• D. W. Cranston and H. LaFayette, The t-tone chromatic number of classes of sparse graphs, Australas. J. Combin. 86 (2023), 458-476.
• N. Fonger, J. Goss, B. Phillips, and C. Segroves, Math 6450: Final Report, Group #2 Study Project, 2009.

Crossrefs

Cf. A350361 (trees), A350362 (cycles), A350715 (wheels), A366728 (cycle squared).

Cf. A003057, A351120 (pair coloring).

Formula

a(n) = ceiling(sqrt(2*n + 1/4) + 5/2) for n > 6.