A381565 2-tone chromatic number of a particular class of planar graphs with 3n+3 vertices.

5, 6, 7, 7, 8, 8, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 21

Offset: 1

Author

Allan Bickle, Feb 27 2025

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.

The graphs are formed by replacing each edge of K_3 by n disjoint paths with length 2, resulting in 3n+3 vertices. These graphs have large 2-tone chromatic number relative to their maximum degree of 2t.

Examples

			For n=1, the graph is a 6-cycle, which has a 2-tone 5-coloring -12-34-15-32-14-35-.  Thus a(1) = 5.
		

Links

• Allan Bickle, 2-Tone coloring of joins and products of graphs, Congr. Numer. 217 (2013) 171-190.
• Allan Bickle, 2-Tone Coloring of Planar Graphs, Bull. Inst. Combin. Appl. 103 (2025) 114-129.
• 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.

Crossrefs

Cf. A003057, A351120 (pair coloring).

Cf. A350361 (trees), A350362 (cycles), A350715 (wheels), A366727 (outerplanar), A366728 (square of cycles), A381562 (maximal planar).

Formula

a(n) = ceiling(1.5 + sqrt(6*n + 6.25)) for n < 18.

a(n) = ceiling(0.5 + sqrt(6*n + 24.25)) for n > 6.