A366728 2-tone chromatic number of the square of a cycle with n vertices.

6, 8, 10, 9, 7, 8, 8, 8, 8, 7, 8, 7, 7, 7, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7

Offset

3,1

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 square of a cycle is formed by adding edges between all vertices at distance 2 in the cycle.

Links

Table of n, a(n) for n=3..85.

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.

Formula

a(n) = 7 for all n>17.

Example

The colorings for (broken) cycles with orders 7 through 13 are shown below.
  -12-34-56-71-23-45-67-
  -12-34-56-78-13-24-57-68-
  -12-34-56-17-23-45-16-37-58-
  -12-34-56-71-23-68-15-24-38-57-
  -12-34-56-17-24-36-58-14-26-38-57-
  -12-34-56-71-32-54-16-37-52-14-36-57-
  -12-34-56-71-32-54-16-37-58-14-32-57-68-

Crossrefs

Cf. A350361 (trees), A350362 (cycles), A350715 (wheels), A366727 (MOPs).

Cf. A003057, A351120 (pair coloring).

Sequence in context: A238621 A099102 A001743 * A256964 A046344 A116366

Adjacent sequences: A366725 A366726 A366727 * A366729 A366730 A366731

Keyword

nonn

Author

Allan Bickle, Oct 17 2023

Status

approved