A381563 2-tone chromatic number of a double wheel graph with n vertices.

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

Offset: 5

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.

A double wheel has two vertices joined to a all vertices of a cycle.

Examples

			The central vertices share exactly one color.  All vertices on the cycle require distinct pairs.
The colorings for small (broken) cycles are shown below.
  -12-34-56-
  -12-34-15-36-
  -12-34-51-23-45-
  -12-34-15-32-14-35-
  -12-34-56-13-24-35-46-
  -12-34-15-23-14-25-13-45-
  -12-34-15-32-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).

Formula

a(n) = A351120(n-2) + 3 = A350715(n-1) + 1.

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