cp's OEIS Frontend

A381564 2-tone chromatic number of a path with n-2 vertices joined to two adjacent vertices.

%I A381564 #4 Feb 28 2025 12:04:43
%S A381564 8,9,9,9,9,9,9,9,9,10,10,10,10,10,11,11,11,11,11,11,12,12,12,12,12,12,
%T A381564 12,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,15,15,15,15,15,
%U A381564 15,15,15,15,15,16,16,16
%N A381564 2-tone chromatic number of a path with n-2 vertices joined to two adjacent vertices.
%C A381564 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 A381564 The graphs are maximal planar.
%H A381564 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 A381564 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 A381564 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.
%F A381564 a(n) = ceiling((9 + sqrt(8*n - 15))/2) for n > 8.
%e A381564 The central vertices each have two disjoint labels.  All vertices on the path require distinct pairs.
%e A381564 The colorings for small paths are shown below.
%e A381564   12-34
%e A381564   12-34-15
%e A381564   12-34-15-23
%e A381564   12-34-15-23-14
%e A381564   12-34-15-23-14-25
%e A381564   12-34-15-23-14-25-13
%e A381564   12-34-15-23-14-25-13-24
%e A381564   12-34-15-23-14-25-13-24-35
%Y A381564 Cf. A003057, A351120 (pair coloring).
%Y A381564 Cf. A350361 (trees), A350362 (cycles), A350715 (wheels), A366727 (outerplanar), A366728 (square of cycles), A381562 (maximal planar), A381563 (double wheels).
%K A381564 nonn
%O A381564 4,1
%A A381564 _Allan Bickle_, Feb 27 2025