A381562 Minimum 2-tone chromatic number of maximal planar graphs with n vertices.

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

Offset: 3

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.

For n in {19,22,23,27}, a(n) is either 7 or 8. All larger values are 7.

Examples

			For n=3, all 3 vertices get two distinct colors, so a(3) = 6.
For n=4, all 4 vertices get two distinct colors, so a(3) = 8.
For n=5 or 6, the extremal graph is a double wheel.
		

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

Formula

a(n) = 7 for n > 27.