cp's OEIS Frontend

A351120 Pair chromatic number of a cycle graph with n vertices.

%I A351120 #19 Nov 30 2023 07:24:17
%S A351120 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 A351120 10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,12,12,12,12,
%U A351120 12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,13,13,13,13,14,14,14,14
%N A351120 Pair chromatic number of a cycle graph with n vertices.
%C A351120 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 A351120 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 A351120 Paolo Xausa, <a href="/A351120/b351120.txt">Table of n, a(n) for n = 3..10000</a>
%H A351120 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 A351120 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 A351120 a(n) = ceiling((1 + sqrt(1 + 8*n))/2) for n > 10.
%e A351120 The colorings for (broken) cycles with orders 3 through 9 are shown below.
%e A351120   -12-34-56-
%e A351120   -12-34-15-36-
%e A351120   -12-34-51-23-45-
%e A351120   -12-34-15-32-14-35-
%e A351120   -12-34-56-13-24-35-46-
%e A351120   -12-34-15-23-14-25-13-45-
%e A351120   -12-34-15-32-14-25-13-24-35-
%t A351120 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 A351120 Cf. A003057, A350361, A350362.
%K A351120 nonn
%O A351120 3,1
%A A351120 _Allan Bickle_, Feb 01 2022