From semi-total to equitable total colorings, and their induced partitions into perfect and total perfect codes

2025

Read From semi-total to equitable total colorings, and their induced partitions into perfect and total perfect codes (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-20055.txt.

Introduction

Dejter studies graph coloring problems in a 2025 math paper. The catalog record lists no creator, while the text byline gives a single author surname. The topic is total coloring, where both points and lines of a graph get colors so that neighbors never share one.

A long-standing conjecture caps the colors needed at one or two above the highest point degree. Dejter starts from partial colorings, called semi-total, and adapts an old swapping method to reach fair total colorings, where color classes stay balanced in size. The work covers symmetric and cage graphs and expansions of cubic graphs. Along the way, color classes form error-correcting codes in several famous graphs, including a split of the ninety-point Foster graph.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

From semi-total to equitable total colorings, and their induced partitions into perfect and total perfect codes Abstract Independently posed by Behzad and Vizing, the Total Coloring Conjecture asserts that the total chromatic number of a connected simple graph G G is either Δ ⁡ ( G ) + 1 \Delta(G)+1 or Δ ⁡ ( G ) + 2 \Delta(G)+2 , where Δ ⁡ ( G ) \Delta(G) is the largest degree of a vertex of G G . Deciding whether a cubic graph G G has total chromatic number Δ ⁡ ( G ) + 1 \Delta(G)+1 , even for bipartite cubic graphs, is NP-hard. The problem persists even for equitable total colorings. Williams and Holroyd gave a condition for total colorings via the introduction of semi-total colorings. In the present work, focus is set on obtaining, by means of a variation of Kempe’s 1879 graph-coloring algorithm, equitable total colorings out of semi-total colorings of: symmetric cubic graphs, cage graphs and expansions of cubic graphs. It is noted that total colorings of the 3-cube and subsequent polygon prisms exist having perfect codes as their vertex color classes, as well as semi-total colorings of Möbius ladders having total perfect codes as their vertex color classes, only one of which, in K 3 , 3 K_{3,3} , being equitable; in addition, a partition into two perfect-codes and one total-perfect code is given by the vertex color classes of the 90-vertex Foster graph. On the other hand, a semi-total coloring of the 42-vertex ( 5 , 6 ) (5,6) -cage yields its decomposition into three copies of the Heawood graph via its edges of same color endvertices and seven remaining 6-cycles. Italo J. Dejter University of Puerto Rico Rio Piedras, PR 00936-8377 [email protected] 1 A variation of Kempe’s coloring algorithm Let \Delta(G) be the largest degree of any vertex of a connected simple graph G . The total coloring (or TC ) conjecture [ 1 , 2 , 31 ] asserts that the total chromatic number \chi^{\prime\prime}(G) of G (see Definition 1 ) is either \Delta(G)+1 or \Delta(G)+2 . To decide whether a cubic graph G has \chi^{\prime\prime}(G)=\Delta(G)+1 , even if G is bipartite cubic, is NP-hard [ 10 , 29 ] . The problem persists even for equitable total colorings, namely those whose color-class cardinalities differ at most by 1; see Subsection 1.2 . Williams and Holroyd [ 32 ] gave a condition to solve TC problems departing from semi-total colorings (or sTC s); see Definition 4 . A variation of Kempe’a 1879 graph-coloring algorithm [ 24 ] (that has applications in Register Allocation [ 4 ] ) is introduced in Theorem 14 , taking semi-total colorings of connected simple graphs and modifying them into equitable total colorings, or in their defect, into equitable semi-total colorings. Theorem 14 and Theorem 19 , this one dealing with covering graph maps, are applied to three families of graphs, namely symmetric cubic graphs (Section 2 ), cage graphs (Examples 28 , 32 , 34 and Section 3 ) and vertex expansions of cubic graphs (Section 4 ). It is to be noted that n -polygon prisms with n>3 have TCs whose color vertex classes are perfect codes (Theorem 27 ) and that Möbius ladders have sTCs whose color vertex classes are total perfect codes via all edges with same color endvertices (Theorem 36 dealing with a generalization of Möbius ladders and Corollary 37 ), where the smallest such ladder, namely the utility graph K_{3,3} , is the only equitable one of them. In addition, the 90-vertex Foster graph has an sTC one of whose color classes is a total perfect code while the other two are perfect codes (Theorem 44 ). Moreover, an sTC of the (5,6) -cage yields its decomposition into three copies of the Heawood graph via all edges with same color endvertices and seven 6-cycles with all remaining edges (Theorem 50 ). We start with some basic definitions. Figure 1: From a lacunar sTC to an EqTC for the 3-cube via \beta -reduction (Example 25 ). 1.1 Total and semi-total colorings Definition 1 . Let G=(V(G),E(G)) be a connected simple graph. A total coloring (or TC ) of G is a color assignment to the elements of G (that is: vertices and edges) such that no two incident or adjacent elements are assigned the same color. Definition 2 . The total chromatic number \chi^{\prime\prime}(G) of a simple connect graph G is the least number of colors needed to color the elements of G such that no two adjacent or incident elements are assigned the same color. A recent survey [ 19 ] contains the most up to date resources on TCs. Recent results on the TC Conjecture are found in [ 10 , 11 , 14 , 28 , 30 ] including that the total chromatic number of cubic graphs is either 4 or 5 [ 14 ] . Definition 3 . A connected simple graph G is of type 1 if \chi^{\prime\prime}(G)=\Delta(G)+1 and is of type 2 if \chi^{\prime\prime}(G)>\Delta(G)+1 , [ 28 , 31 ] . Yap [ 34 ] showed that: (a) a cycle C_{n} is of type 1 if and only if n is a multiple of 3; (b) a complete graph K_{n} is of type 1 if and only if n is odd. Definition 4 . Given a connected simple graph G with maximum degree \Delta , a semi-total coloring (or sTC ) \mu of G is a function \mu:V(G)\cup E(G)\rightarrow\chi(\Delta)=\{1,2,\ldots,\Delta+1\} , where \chi(\Delta) is the assumed set of colors for G , such that every two adjacent edges of G have distinct colors of \chi(\Delta) and every vertex of G has a color in \chi(\Delta) distinct from the colors of its incident edges. The concept of an sTC is similar to that of a TC, except that it is not required that adjacent vertices have distinct colors. The need of using \Delta+1 colors to obtain an sTC for G emerges because at least \Delta+1 colors are needed, and by Vizing’s Theorem [ 31 ] , G has an edge coloring with at most \Delta+1 colors, so that there is at least one color free for each vertex. Definition 5 . Given a connected simple graph G and an sTC \mu of G , an edge v_{0}v_{1} of G such that \mu(v_{0})=\mu(v_{1}) is said to be a \beta -edge of G with respect to (or wrt ) \mu . The number of \beta -edges of G wrt \mu is denoted by \beta(\mu) . Definition 6 . Given a connected simple graph G and an sTC \mu of G , the minimum value of \beta(\mu) over all sTCs \mu of G is said to be the beta parameter \beta(G) of G . Figure 2: From a lacunar sTC to an EqTC for the Heawood graph (Example 28 ). Williams and Holroyd [ 32 ] showed that: (a) if n\equiv 1 or 2 (mod 3), then \beta(C_{n})=2 ; (b ) if n is even, then \beta(K_{n})=n/2 . 1.2 Equitable total coloring Definition 7 . Let G be a connected simple graph and let \mu be a TC of G . The \mu -class of a color i\in\chi(\Delta) is the subset

Read the complete text