A381564 2-tone chromatic number of a path with n-2 vertices joined to two adjacent vertices.

8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16

Offset: 4

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 maximal planar.

Examples

			The central vertices each have two disjoint labels.  All vertices on the path require distinct pairs.
The colorings for small paths are shown below.
  12-34
  12-34-15
  12-34-15-23
  12-34-15-23-14
  12-34-15-23-14-25
  12-34-15-23-14-25-13
  12-34-15-23-14-25-13-24
  12-34-15-23-14-25-13-24-35
		

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.

Crossrefs

Cf. A003057, A351120 (pair coloring).

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

Formula

a(n) = ceiling((9 + sqrt(8*n - 15))/2) for n > 8.