A351120 - OEIS

%I #19 Nov 30 2023 07:24:17

%S 6,6,5,5,6,5,5,6,6,6,6,6,6,7,7,7,7,7,7,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,

%T 10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,12,12,12,12,

%U 12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,13,13,13,13,14,14,14,14

%N Pair chromatic number of a cycle graph with n vertices.

%C The pair 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 colors is repeated.

%C There is no pair 5-coloring for cycles of length 3, 4, 7, or 10 since the Petersen graph does not contain cycles of these lengths.

%H Paolo Xausa, <a href="/A351120/b351120.txt">Table of n, a(n) for n = 3..10000</a>

%H Allan Bickle, <a href="https://allanbickle.files.wordpress.com/2016/05/2tonejcpaper.pdf">2-Tone coloring of joins and products of graphs</a>, Congr. Numer., Vol. 217 (2013), pp. 171-190.

%H Allan Bickle and Ben Phillips, <a href="https://allanbickle.files.wordpress.com/2016/05/ttonepaperb.pdf">t-Tone Colorings of Graphs</a>, Utilitas Math, Vol. 106 (2018), pp. 85-102.

%F a(n) = ceiling((1 + sqrt(1 + 8*n))/2) for n > 10.

%e The colorings for (broken) cycles with orders 3 through 9 are shown below.

%e   -12-34-56-

%e   -12-34-15-36-

%e   -12-34-51-23-45-

%e   -12-34-15-32-14-35-

%e   -12-34-56-13-24-35-46-

%e   -12-34-15-23-14-25-13-45-

%e   -12-34-15-32-14-25-13-24-35-

%t A351120[n_]:=If[n<11,{6,6,5,5,6,5,5,6}[[n-2]],Ceiling[(1+Sqrt[1+8n])/2]];Array[A351120,100,3] (* _Paolo Xausa_, Nov 30 2023 *)

%Y Cf. A003057, A350361, A350362.

%K nonn

%O 3,1

%A _Allan Bickle_, Feb 01 2022