List rainbow connection number of graphs

Rongxia Tang, Henry Liu, Yueping Shi, Chenming Wang · 2025

Read List rainbow connection number of graphs by Rongxia Tang, Henry Liu, Yueping Shi, Chenming Wang (2025) 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-2503-08964.txt.

Introduction

Rongxia Tang, Henry Liu, Yueping Shi, and Chenming Wang introduce list versions of rainbow connection numbers in a twenty twenty-five mathematics paper. In a rainbow path, every edge carries a different colour. Classic measures count the fewest colours that link every pair of vertices by such a path. The list versions let each edge choose from its own allowed colour list.

Results give the new numbers for several specific graphs. The authors also sort out which pairs of values can occur together. One pair links the ordinary and strong list measures. Another links the strong measure with its list form. The paper closes by asking whether the ordinary and list numbers always match.

Catalog record

CREATORRongxia Tang, Henry Liu, Yueping Shi, Chenming Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-08964

Browse the full library · About the Tower of Babel

Full text

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

List rainbow connection number of graphs Rongxia Tang, Henry Liu, Yueping Shi, Chenming Wang Abstract An edge-coloured path is rainbow if all of its edges have distinct colours. Let G G be a connected graph. The rainbow connection number of G G , denoted by r ​ c ​ ( G ) rc(G) , is the minimum number of colours in an edge-colouring of G G such that, any two vertices are connected by a rainbow path. The strong rainbow connection number of G G , denoted by s ​ r ​ c ​ ( G ) src(G) , is the minimum number of colours in an edge-colouring of G G such that, any two vertices are connected by a rainbow geodesic (i.e., a path of shortest length). These two notions of connectivity of graphs were introduced by Chartrand, Johns, McKeon and Zhang in 2008. In this paper, we introduce the list rainbow connection number r ​ c ℓ ​ ( G ) rc^{\ell}(G) , and the list strong rainbow connection number s ​ r ​ c ℓ ​ ( G ) src^{\ell}(G) . These two parameters are the versions of r ​ c ​ ( G ) rc(G) and s ​ r ​ c ​ ( G ) src(G) that involve list edge-colourings. Among our results, we will determine the list rainbow connection number and list strong rainbow connection number of some specific graphs. We will also characterise all pairs of positive integers a a and b b such that, there exists a connected graph G G with s ​ r ​ c ​ ( G ) = a src(G)=a and s ​ r ​ c ℓ ​ ( G ) = b src^{\ell}(G)=b , and similarly for the pair r ​ c ℓ rc^{\ell} and s ​ r ​ c ℓ src^{\ell} . Finally, we propose the question of whether or not we have r ​ c ​ ( G ) = r ​ c ℓ ​ ( G ) rc(G)=rc^{\ell}(G) , for all connected graphs G G . AMS Subject Classification (2020): 05C15 Keywords: List colouring; (strong) rainbow connection number 1 Introduction In this paper, all graphs are finite, simple, and undirected. Let K_{n} and C_{n} denote the complete graph and cycle on n vertices. Let K_{n_{1},\dots,n_{t}} denote the complete t -partite graph with class sizes n_{1},\dots,n_{t} . In particular, K_{m,n} is the complete bipartite graph with class sizes m and n . For t_{1},t_{2},\ldots\geq 0 , let K_{t_{1}\times 1,t_{2}\times 2,\dots} denote the complete multipartite graph with t_{i} classes of size i , for all i\geq 1 . Any subscript with t_{i}=0 is usually omitted. In particular, K_{t\times n} denotes the complete t -partite graph where every class has size n . For a graph G , a vertex v\in V(G) , and a subset S\subset V(G) , let \Gamma_{G}(v)=\{u\in V(G):uv\in E(G)\} and \Gamma_{G}(S)=\bigcup_{w\in S}\Gamma_{G}(w) denote the open neighbourhood of v and S ; and let d_{G}(v)=|\Gamma_{G}(v)| denote the degree of v . Let G-v denote the subgraph obtained by deleting v and all edges at v from G . For a subset of edges E\subset E(G) , let G-E denote the subgraph (V(G),E(G)\setminus E) . For two vertices x,y\in V(G) , let d_{G}(x,y) denote the distance from x to y in G , and diam (G)=\max\{d_{G}(x,y):x,y\in V(G)\} denote the diameter of G . For any other undefined terms in graph theory, we refer to the book by Bollobás [ 2 ] . Throughout, let r\geq 1 be a positive integer. An r -colouring (or simply colouring ) of a graph G is a function c:V(G)\to[r] , where [r]=\{1,\dots,r\} , and c is proper if c(u)\neq c(v) for all uv\in E(G) . We think of [r] as a set of colours, and each vertex of G is given one of r possible colours. The chromatic number \chi(G) of G is the minimum integer r such that there exists a proper r -colouring of G . A list colouring of G is a generalisation of a colouring, where each vertex of G has a prescribed list of colours, and may only be assigned a colour from its own list. The notion of list colouring was introduced in the late 1970s, independently by Vizing [ 15 ] , and by Erdős, Rubin and Taylor [ 8 ] . More precisely, an r -list assignment of G is a function L:V(G)\to\mathbb{N}^{(\geq r)} , where \mathbb{N}^{(\geq r)} denotes the family of all subsets of \mathbb{N} with at least r elements. For v\in V(G) , a set L(v) is a list . An L -colouring of G is a function c:V(G)\to\mathbb{N} such that c(v)\in L(v) for all v\in V(G) , and c is proper if c(u)\neq c(v) for all uv\in E(G) . We say that G is r -choosable if for every r -list assignment L of G , there exists an L -colouring of G which is proper. The list chromatic number \chi_{\ell}(G) of G is the minimum integer r such that G is r -choosable. The parameter \chi_{\ell}(G) may also be denoted by ch(G) , and may be called the choice number of G . Clearly, we have \chi(G)\leq\chi_{\ell}(G) . Equality does not necessarily hold. For example, we have \chi(K_{m,n})=2 . A result of Erdős, Rubin and Taylor [ 8 ] states that \chi_{\ell}(K_{p,p})>r if p={2r-1\choose r} . Another well-known result from the 1970s states that \chi_{\ell}(K_{p,p^{p}})=p+1 for p\geq 1 . The edge-colouring formulations are very much analogous. An r -edge-colouring (or simply edge-colouring or colouring ) of G is a function c:E(G)\to[r] , and c is proper if c(e)\neq c(f) for any two incident edges e,f\in E(G) . The edge-chromatic number (or chromatic index ) \chi^{\prime}(G) of G is the minimum integer r such that there exists a proper r -edge-colouring. An r -edge-list assignment of G is a function L:E(G)\to\mathbb{N}^{(\geq r)} . For e\in E(G) , a set L(e) is a list . An L -edge-colouring of G is a function c:E(G)\to\mathbb{N} such that c(e)\in L(e) for all e\in E(G) , and c is proper if c(e)\neq c(f) for any two incident edges e,f\in E(G) . The list edge-chromatic number \chi_{\ell}^{\prime}(G) of G is the minimum integer r such that, for all r -edge-list assignment L of G , there exists a proper L -edge-colouring. We have \chi^{\prime}(G)\leq\chi_{\ell}^{\prime}(G) . While we may possibly have \chi(G)<\chi_{\ell}(G) for some graph G , the famous list colouring conjecture , which first appeared in print in a paper of Bollobás and Harris [ 3 ] , states that \chi^{\prime}(G)=\chi_{\ell}^{\prime}(G) for every graph G . The rainbow connection number , introduced by Chartrand, Johns, McKeon and Zhang [ 4 ] in 2008, is a graph colouring parameter that has recently received significant interest. A path connecting two vertices u,v of a connected graph G is a geodesic if it has the shortest possible length, i.e., d_{G}(u,v) . An edge-coloured path is rainbow if its edges have distinct colours. An edge-colouring (not necessarily proper) of a connected graph G is rainbow connected (resp. strongly rainbow connected ) if any two vertices of G are connected by a rainbow path (resp. rainbow geodesic). The rainbow connection number rc(G) and strong rainbow connection number src(G) are,

Read the complete text