The edge chromatic transformation index of graphs
Armen S. Asratian, Carl Johan Casselgren · 2025
Read The edge chromatic transformation index of graphs by Armen S. Asratian, Carl Johan Casselgren (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-2512-01614.txt.
Introduction
Armen Asratian and Carl Johan Casselgren study an edge coloring transform index for graphs. Edge coloring paints edges so touching edges differ. The transform index is the least steps to turn any valid coloring into any other. Steps recolor one edge at a time while staying valid.
That index tells how flexible a coloring system is. Low values mean colorings can be reshaped with ease. The work builds theory for that index across graphs. Flexible recoloring matters for scheduling and network tasks where colors must shift without breaking rules. Recoloring steps mirror live network upkeep, where links change class as loads shift but service rules must hold at every step between.
Catalog record
| CREATOR | Armen S. Asratian, Carl Johan Casselgren |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-01614
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The edge chromatic transformation index of graphs Armen S. Asratian, Carl Johan Casselgren Abstract Given a graph or multigraph G G , let χ t r a n s ′ ( G ) \chi^{\prime}_{trans}(G) denote the minimum integer n n such that any proper χ ′ ( G ) \chi^{\prime}(G) –edge coloring of G G can be transformed into any other proper χ ′ ( G ) \chi^{\prime}(G) –edge coloring of G G by a series of transformations such that each of the intermediate colorings is a proper χ ′ ( G ) \chi^{\prime}(G) –edge coloring of G G and each of the transformations involves at most n n color classes of the previous coloring. We call χ t r a n s ′ ( G ) \chi^{\prime}_{trans}(G) the edge chromatic transformation index of G G . In this paper we show that if G G is a graph with maximum degree at least 4 4 , where every block is either a bipartite graph, a series-parallel graph, a chordless graph, a wheel graph or a planar graph of girth at least 7 7 , then χ t r a n s ′ ( G ) ≤ 4 \chi^{\prime}_{trans}(G)\leq 4 . This bound is sharp for series-parallel and wheel graphs. We also show that χ t r a n s ′ ( G ) ≤ 8 \chi^{\prime}_{trans}(G)\leq 8 for all planar graphs G G , χ t r a n s ′ ( G ) ≤ 5 \chi^{\prime}_{trans}(G)\leq 5 if G G is a Halin graph and χ t r a n s ′ ( G ) = 2 \chi^{\prime}_{trans}(G)=2 if G G is a regular bipartite planar multigraph. Finally, we consider the analogous problem for vertex colorings, and show that for any k ≥ 3 k\geq 3 there is an infinite class 𝒢 \cal G ( k ) (k) of graphs with chromatic number k k such that for every G ∈ 𝒢 G\in\cal G ( k ) (k) any two proper k k -vertex colorings of G G can be transformed to each other only by a transformation, involving all k k color classes. Keywords: Edge coloring, transformation, Kempe equivalence, Halin graph, chordless graph, series-parallel graph. 1 Introduction Edge coloring problems appear in many places with seemingly no or little connections to graph coloring [ 3 , 6 , 7 , 11 , 15 , 18 ] . For example, many problems on school timetables can be formulated in terms of edge colorings of bipartite graphs and multigraphs [ 4 , 27 ] . Some optimization problems formulated in terms of edge colorings are NP-hard and therefore handled with heuristic algorithms. Usually the underlying search problem is solved and the resulting feasible solution (a proper coloring) is used as a starting point to obtain a better solution. Therefore we need some types of transformations which transform one proper coloring (timetable) to any other proper coloring (timetable). Moreover it is convenient to change colorings partly using as few color classes as possible. In this paper, graphs are finite, undirected, without loops and multiple edges. In multigraphs multiple edges are allowed but not loops. A t -edge coloring or simply t -coloring of a graph or multigraph G=(V(G),E(G)) is a mapping f:E(G)\longrightarrow\{1,\dots,t\} . If e\in E(G) and f(e)=j then we say that the edge e is colored j . The set of edges of color j , denoted by M(f,j) , is called a color class , j=1,\dots,t . A t -coloring of G is called proper if no adjacent edges receive the same color. The minimum number t for which there exists a proper t -coloring of G is called the chromatic index of G and is denoted by \chi^{\prime}(G) . We shall say that two distinct t -colorings f and g differ by n color classes if there is a set of colors S of size n , such that M(f,j)\not=M(g,j) for each j\in S , but M(f,j)=M(g,j) for each j\notin S . Definition . Let f and g be two proper t -colorings of a graph G . We will say that f is obtained from g by a series of n -transformations , and g and f are n -equivalent , if there is a sequence of proper t -colorings f_{0},f_{1},\dots,f_{k} of G such that k\geq 1 , f_{0}=f,f_{k}=g and f_{i} differs from f_{i-1} by at most n color classes, i=1,\dots,k . A 2 -transformation is called a Kempe change or interchange , and 2 -equivalence of colorings is known as Kempe-equivalence . Vizing [ 25 ] proved that for every graph G , \chi^{\prime}(G)\leq\Delta(G)+1 , where \Delta(G) denotes the maximum degree of the vertices of G . This implies that for any graph G , either \chi^{\prime}(G)=\Delta(G) or \chi^{\prime}(G)=\Delta(G)+1 . In the former case G is said to be Class 1 , and in the latter G is Class 2 . Investigations of transformations of proper edge colorings mostly concern two problems. The first of them is due to Vizing [ 25 , 26 ] who showed that any proper edge coloring of a graph G can be transformed to a proper (\Delta(G)+1) -coloring of G by using Kempe changes only, and posed the following problem: Problem 1.1 . Is it true that any Class 1 graph G satisfies the following property: every proper t -coloring of G , t\geq\Delta(G)+1 , can be transformed to a proper \Delta(G) -coloring of G by a sequence of Kempe changes? The second problem was posed by Mohar [ 20 ] . Problem 1.2 . Is it true that all proper (\chi^{\prime}(G)+1) -colorings of a graph G are Kempe-equivalent? Asratian and Casselgren showed that in fact Problems 1.1 and 1.2 have the same answer (see [ 2 ] , Theorem 1.1). It was successively proved that the answers to Problems 1.1 and 1.2 are positive if either \Delta(G)=3 (McDonald, Mohar and Scheide [ 19 ] ), \Delta(G)=4 (Asratian and Casselgren [ 2 ] ), \Delta(G)\geq 9 and G is a planar graph (Cranston [ 12 ] ), G is triangle-free graph (Bonamy et al [ 9 ] ). In 2023 Narboni [ 21 ] published a preprint with a proof that the answers to Problems 1.1 and 1.2 are positive. A few results are known on Kempe-equivalence of proper \chi^{\prime}(G) -colorings of a graph G : It was proved that all proper \chi^{\prime}(G) -colorings of a graph G are Kempe-equivalent if G is a planar graph with \Delta(G)\geq 15 [ 12 ] , or a 3-regular planar bipartite multigraph [ 8 ] . It is also known that there are infinite classes of graphs G whose proper \chi^{\prime}(G) -colorings are not Kempe-equivalent [ 8 , 20 ] . Therefore, it is natural to introduce the following parameter: Given a graph or multigraph G , let \chi^{\prime}_{trans}(G) denote the minimum integer n\geq 2 such that any proper \chi^{\prime}(G) –coloring of G can be transformed into any other proper \chi^{\prime}(G) –coloring of G by a series of n