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,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.

a(n) is also the 2-tone chromatic number of a fan with n+1 vertices.

Links

Table of n, a(n) for n=1..73.

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) = ceiling(sqrt(2*n + 1/4) + 5/2) for n > 6.

Example

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.

Crossrefs

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

Cf. A003057, A351120 (pair coloring).

Sequence in context: A309606 A288179 A198882 * A000703 A266148 A011275

Adjacent sequences: A366724 A366725 A366726 * A366728 A366729 A366730

Keyword

nonn

Author

Allan Bickle, Oct 17 2023

Status

approved