cp's OEIS Frontend

A381565 2-tone chromatic number of a particular class of planar graphs with 3n+3 vertices.

%I A381565 #4 Feb 28 2025 12:04:50
%S A381565 5,6,7,7,8,8,9,9,10,10,10,11,11,11,12,12,12,12,13,13,13,13,14,14,14,
%T A381565 14,15,15,15,15,15,16,16,16,16,16,17,17,17,17,17,18,18,18,18,18,18,19,
%U A381565 19,19,19,19,19,20,20,20,20,20,20,21
%N A381565 2-tone chromatic number of a particular class of planar graphs with 3n+3 vertices.
%C A381565 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.
%C A381565 The graphs are formed by replacing each edge of K_3 by n disjoint paths with length 2, resulting in 3n+3 vertices.  These graphs have large 2-tone chromatic number relative to their maximum degree of 2t.
%H A381565 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. 217 (2013) 171-190.
%H A381565 Allan Bickle, <a href="https://bica.the-ica.org/Volumes/103//Reprints/BICA2023-46-Reprint.pdf">2-Tone Coloring of Planar Graphs</a>, Bull. Inst. Combin. Appl. 103 (2025) 114-129.
%H A381565 Allan Bickle and B. Phillips, <a href="https://allanbickle.files.wordpress.com/2016/05/ttonepaperb.pdf">t-Tone Colorings of Graphs</a>, Utilitas Math, 106 (2018) 85-102.
%H A381565 D. W. Cranston and H. LaFayette, <a href="https://ajc.maths.uq.edu.au/pdf/86/ajc_v86_p458.pdf">The t-tone chromatic number of classes of sparse graphs</a>, Australas. J. Combin. 86 (2023) 458-476.
%F A381565 a(n) = ceiling(1.5 + sqrt(6*n + 6.25)) for n < 18.
%F A381565 a(n) = ceiling(0.5 + sqrt(6*n + 24.25)) for n > 6.
%e A381565 For n=1, the graph is a 6-cycle, which has a 2-tone 5-coloring -12-34-15-32-14-35-.  Thus a(1) = 5.
%Y A381565 Cf. A003057, A351120 (pair coloring).
%Y A381565 Cf. A350361 (trees), A350362 (cycles), A350715 (wheels), A366727 (outerplanar), A366728 (square of cycles), A381562 (maximal planar).
%K A381565 nonn
%O A381565 1,1
%A A381565 _Allan Bickle_, Feb 27 2025