t-tone colorings of outerplanar and Halin graphs

Hadeel Al Bazzal, Olivier Togni · 2026

Read t-tone colorings of outerplanar and Halin graphs by Hadeel Al Bazzal, Olivier Togni (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18674.txt.

Introduction

Al Bazzal and Togni study t-tone colorings of two planar graph classes. Each vertex gets a set of t colors, and near vertices must share few colors. They fully pin down the 2-tone chromatic number for subcubic outerplanar graphs. For the 3-tone number of the same class, they give a sharp upper bound. For Halin graphs, every cubic one with at least six vertices is 2-tone 7-colorable. They also bound the 2-tone number for Halin graphs with any maximum degree.

Catalog record

CREATORHadeel Al Bazzal, Olivier Togni
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42878
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.18674

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

t-tone colorings of outerplanar and Halin graphs Hadeel Al Bazzal, Olivier Togni Abstract A t t -tone k k -coloring of a graph G G assigns a set of t t distinct colors from { 1 , … , k } \{1,\dots,k\} to each vertex so that vertices at distance d d share fewer than d d common colors. The t t -tone chromatic number of G G is the minimum k k such that G G has a t t -tone k k -coloring. This paper investigates the t t -tone coloring of two specific subclasses of planar graphs: subcubic outerplanar graphs and Halin graphs. We provide a complete characterization of the 2 2 -tone chromatic number for subcubic outerplanar graphs and establish a sharp upper bound for their 3 3 -tone chromatic number. We then turn to Halin graphs and prove that every cubic Halin graph of order n ≥ 6 n\geq 6 is 2 2 -tone 7 7 -colorable. Moreover, we derive an upper bound on the 2 2 -tone chromatic number for Halin graphs with arbitrary maximum degree. Keywords: t -tone coloring, t -tone chromatic number, subcubic graph, outerplanar graph, Halin graph. AMS Subject Classification: 05C15 1 Introduction All graphs considered in this paper are assumed to be simple and finite. For a graph G , we let V(G) denote its vertex set. The minimum degree and maximum degree of G are denoted by \delta(G) and \Delta(G) , respectively. For any distinct vertices u,v\in V(G) , the distance between u and v in G , denoted by d_{G}(u,v) , is the length of a shortest uv -path in G . The degree of a vertex v is denoted by d_{G}(v) . The neighbors of v are the vertices at distance one from v , and the second neighbors of v are the vertices at distance two from v , forming the set N_{G}^{2}(v) . We write C_{n} , P_{n} , and K_{n} for the cycle, path, and complete graph on n vertices, respectively. The wheel graph W_{d} is obtained by joining a single vertex to every vertex of a cycle C_{d-1} . We denote by \binom{\{1,\dots,k\}}{t} the family of all t -element subsets of \{1,\dots,k\} . A graph G is subcubic if \Delta(G)\leq 3 . An outerplanar graph is a graph that admits a planar embedding in which every vertex lies on the boundary of the outer face. In such an embedding, all bounded regions are called bounded faces. Furthermore, a Halin graph H=T\cup C is a plane graph consisting of a tree T with no vertices of degree two, and a cycle C that connects the leaves of T according to the cyclic order imposed by the planar embedding of T . The primary focus of this paper is the t -tone k -coloring, a generalization of proper coloring. Definition 1.1 . Let G be a graph, and let t and k be positive integers with t\leq k . A t -tone k -coloring of G is a function f\colon V(G)\to\binom{\{1,\dots,k\}}{t} such that |f(u)\cap f(v)|<d_{G}(u,v) for all distinct vertices u,v\in V(G) . A graph G that admits a t -tone k -coloring is said to be t -tone k -colorable . The t -tone chromatic number of G , denoted \tau_{t}(G) , is the smallest integer k for which G is t -tone k -colorable. For a given t -tone coloring f , we call f(v) the label of v , and the elements within \{1,\dots,k\} colors. To simplify the notation, we frequently omit set brackets and commas; for instance, we write ab instead of \{a,b\} and abc instead of \{a,b,c\} . Observe that for any fixed t , the parameter \tau_{t} is monotone: if H\subseteq G , then \tau_{t}(H)\leq\tau_{t}(G) . The notion of t -tone k -coloring was introduced by Chartrand and first studied in a research group directed by Zhang, consisting of Fonger, Goss, Phillips, and Segroves [ 13 ] . It was then thoroughly explored by Bickle and Phillips [ 7 ] . The most widely studied case of t -tone coloring is when t=2 . In this setting, each vertex is assigned a 2 -element label such that adjacent vertices receive disjoint labels, and vertices at distance two receive distinct labels. Several basic results follow immediately; for instance, \tau_{2}(K_{n})=2n and \tau_{2}(K_{4}-e)=7 . For cubic graphs, Bickle and Phillips [ 7 ] proposed the following conjecture. Conjecture 1.1 . Let G be a cubic graph. Then: 1. \tau_{2}(G)\leq 8 . 2. If G does not contain K_{4} , then \tau_{2}(G)\leq 7 . 3. If G does not contain K_{4}-e , then \tau_{2}(G)\leq 6 . In [ 9 ] , Cranston, Kim, and Kinnersley confirmed the first part of the conjecture and disproved the third by presenting a counterexample, namely the Heawood graph, which does not contain K_{4}-e . Since then, 2 -tone coloring has been investigated for several graph classes, including cycles [ 7 ] , trees [ 13 , 7 ] , wheels [ 3 ] , and others [ 1 , 2 , 4 , 5 , 6 , 7 , 9 , 10 , 11 , 12 , 16 , 17 ] . Moreover, 2 -tone colorings of graph products were studied in [ 3 , 8 , 14 ] . General upper bounds for the 2 -tone chromatic number were established in [ 3 , 9 , 10 , 11 , 12 ] , while lower bounds were considered in [ 15 ] . Finally, t -tone coloring for general values of t has been explored in [ 10 , 16 , 17 ] . In this paper, we investigate the t -tone coloring of subcubic outerplanar graphs and Halin graphs. The paper is organized as follows. In Section 2 , we examine subcubic outerplanar graphs. We show that a subcubic outerplanar graph G admits a 2 -tone 5 -coloring if and only if G contains no cycles of length 3 , 4 , or 7 . Then we prove that a subcubic outerplanar graph G admits a good 2 -tone 6 -coloring if and only if G does not contain K_{4}-e , where a good 2 -tone k -coloring is a 2 -tone k -coloring in which any two vertices at distance two share exactly one color. These results together yield a complete characterization of the 2 -tone chromatic number of connected subcubic outerplanar graphs of order n\geq 3 . Theorem 1.1 . Let G be a connected subcubic outerplanar graph of order n\geq 3 . Then \tau_{2}(G)=\begin{cases}5,&\text{if }G\text{ contains no }C_{3},C_{4},C_{7},\\ 6,&\text{if }G\text{ contains one of }C_{3},C_{4},C_{7}\text{ but no }K_{4}-e,\\ 7,&\text{otherwise}.\end{cases} Next, we establish a sharp upper bound for the 3 -tone chromatic number of subcubic outerplanar graphs by proving that \tau_{3}(G)\leq 11 for every such graph G . Rather than working directly with 3 -tone colorings, we introduce a strengthened coloring framework, called a 3 -good k -coloring , which assigns a set of three colors from \{1,2,\dots,k\} to each vertex of G such that any two adjacent vertices share no colors, and any two vertices at distance two share exactly one color. This exact intersection condition ensures that all 3 -tone constraints are automatically

Read the complete text