Total coloring graphs with large minimum degree

Owen Henderschedt, Jessica McDonald, Songling Shan · 2025

Read Total coloring graphs with large minimum degree by Owen Henderschedt, Jessica McDonald, Songling Shan (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-2507-05548.txt.

Introduction

Owen Henderschedt, Jessica McDonald, and Songling Shan prove a case of a long-standing guess about coloring graphs. In a total coloring, both the points of a graph and the lines joining them get colors, and neighbours — including a point and its own lines — must all differ. The Total Coloring Conjecture caps the colors needed at the largest number of lines at any point, plus two, but the guess has resisted proof in general.

The team settles it for very dense graphs. For any fixed margin, once a graph is large enough and every point touches at least half the other points, with a little room to spare, the cap holds. Density, in other words, gives enough structure to force the coloring through.

Catalog record

CREATOROwen Henderschedt, Jessica McDonald, Songling Shan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-05548

Browse the full library · About the Tower of Babel

Full text

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

Total coloring graphs with large minimum degree Owen Henderschedt, Jessica McDonald, Songling Shan Abstract We prove that for all ε > 0 \varepsilon>0 , there exists a positive integer n 0 n_{0} such that if G G is a graph on n ≥ n 0 n\geq n_{0} vertices with δ ⁡ ( G ) ≥ 1 2 ​ ( 1 + ε ) ​ n \delta(G)\geq\tfrac{1}{2}(1+\varepsilon)n , then G G satisfies the Total Coloring Conjecture, that is, χ T ​ ( G ) ≤ Δ ⁡ ( G ) + 2 \chi_{T}(G)\leq\Delta(G)+2 . 1 Introduction A total coloring of a graph G is an assignment of colors to both the edges and vertices of G so that the coloring on the edges induces an edge-coloring, and the coloring on the vertices induces a vertex-coloring, and an incident edge and vertex must also receive different colors. The total chromatic number of G , denoted \chi_{T}(G) , is the minimum number of colors needed for a total coloring of G . In this paper we use the term ‘graph’ to mean simple graph, and will explicitly say ‘multigraph’ when parallel edges are allowed; loops will not appear in this paper. For terms not defined here, we follow [ 25 ] . The Total Coloring Conjecture , proposed independently by Behzad [ 1 ] and Vizing [ 24 ] in the 1960’s, asserts that \chi_{T}(G)\leq\Delta(G)+2 for every graph G , where \Delta(G) is the maximum degree of G . Note that since a vertex of maximum degree must receive different colors from all its incident edges, every graph G satisfies \chi_{T}(G)\geq\Delta(G)+1 . The conjecture is therefore a natural analog of Vizing’s Theorem which states that \Delta(G)\leq\chi^{\prime}(G)\leq\Delta(G)+1 , where \chi^{\prime}(G) is the chromatic index of G . Determining each of \chi_{T}(G) and \chi^{\prime}(G) exactly is known to be NP-hard [ 13 , 21 ] . There is a large literature towards the Total Coloring Conjecture that we will not survey; the interested reader is referred to [ 4 , 6 , 14 ] . Relevant to our discussion here is that the conjecture appears to get easier as the maximum degree increases, particularly when the graph is regular. In 1993 Hilton and Hind [ 12 ] confirmed the Total Coloring Conjecture for all graphs with \Delta(G)\geq\frac{3}{4}|V(G)| . Recently the second and third authors, along with Dalal, lowered this bound to almost \frac{1}{2}|V(G)| for sufficiently large regular graphs [ 4 ] . In this paper we extend that result in two directions, by replacing \Delta(G) with minimum degree \delta(G) and by removing the requirement of regularity. Theorem 1 . For all \varepsilon>0 , there exists n_{0}\in\mathbb{N} such that if G is a graph on n\geq n_{0} vertices with \delta(G)\geq\tfrac{1}{2}(1+\varepsilon)n , then \chi_{T}(G)\leq\Delta+2 . Let G be a graph, and let M be a matching in the complement \overline{G} of G . Define G^{M} as the graph obtained from G by first adding one new vertex x , and then adding both the edges of M and the edges of E(x)=\{xu:u\in V(G)\setminus V(M)\} . We say an edge-coloring \varphi of G^{M} is good if \varphi has at most \Delta(G)+2 colors and each edge of M\cup E(x) is colored with a different color under \varphi . Note that a good edge-coloring of G^{M} immediately leads to a total coloring of G with at most \Delta(G)+2 colors, because the auxiliary edge-colors can be used on the vertices of G . Our proof of Theorem 1 has two main parts: first we reduce Theorem 1 to two different cases for G,M , and then we show that both of these cases lead to G^{M} having a good edge-coloring. Section 2 of this paper contains our reduction, which relies on some classic results of Hajnal and Szemerédi [ 9 ] , Hakimi [ 11 ] , Vizing and Gupta [ 23 , 8 ] and Tutte and Berge [ 22 , 2 ] along with some more recent work of Shan [ 19 ] and Plantholt and Shan [ 18 ] . Section 3 contains a new lemma about edge-coloring certain multigraphs so that specific edges are guaranteed to have different colors. Section 4 uses this lemma to complete the proof of Theorem 1 , namely by showing that G^{M} has a good edge-coloring in both of the cases we have reduced to. 2 Reduction Let G be an n -vertex graph, and define V_{\delta}(G) to be the set of all minimum-degree vertices in G , that is, V_{\delta}(G)=\{v\in V(G)|d_{G}(v)=\delta(G)\} . For v\in V(G) , we say it has middle-degree if \delta(G)<d_{G}(v)<\Delta(G) . Finally, for any \xi>0 we define U_{\xi}(G)=\{u\in V(G)|\Delta(G)-d_{G}(u)\geq\xi n\}; we can think of U_{\xi}(G) as being those vertices in G of sufficiently small degree. Consider the following theorem. Theorem 2 . For all \varepsilon>0 , there exists \xi with 0<\xi\ll\varepsilon and n_{0}\in\mathbb{N} such G^{M} has a good edge-colouring, provided G,M satisfy all of the following: (a) G is a graph on n\geq n_{0} vertices with \delta(G)\geq\tfrac{1}{2}(1+\varepsilon)n and \Delta(G)<\frac{3}{4}n ; (b) M is a matching in \overline{G} , and; (c) G,M lies in one of the following two cases: (1) |M|=\lfloor\frac{n}{2}-0.1\varepsilon n\rfloor and either G is regular or |V_{\delta}(G)|<\xi n , the quantity n-|V_{\delta}(G)| is odd, and G has no middle-degree vertices; (2) |M|\in\{\lfloor\frac{n}{2}-0.1\varepsilon n\rfloor,n-1-\Delta(G)\} and |U_{\xi}(G)|\geq\xi n . We shall prove in this section that Theorem 2 implies Theorem 1 . In order to do so, we’ll need the following four classic results. Theorem 3 (Hakimi [ 11 ] ) . Let 0\leq d_{n}\leq\ldots\leq d_{1} be integers. Then there exists a multigraph G on vertices v_{1},v_{2},\ldots,v_{n} such that d_{G}(v_{i})=d_{i} for all i\in[1,n] if and only if \sum\limits_{i=1}^{n}d_{i} is even and \sum\limits_{i=2}^{n}d_{i}\geq d_{1} . Theorem 4 (Dirac [ 5 ] ) . If G is an n -vertex graph with n\geq 3 and \delta(G)\geq\tfrac{n}{2} , then G has a Hamilton cycle. Theorem 5 (Hajnal and Szemerédi [ 10 ] ) . Let G be a graph and let k\geq\Delta(G)+1 be any integer. Then G has an equitable k -coloring, that is, a k -coloring where the number of vertices in any two distinct color classes differ by at most one. Theorem 6 (Gupta [ 8 ] and Vizing [ 23 ] ) . Every multigraph G satisfies \chi^{\prime}(G)\leq\Delta(G)+\mu(G) . Let k\geq 0 be an integer. A k -edge-coloring of a multigraph G is said to be equalized if each color class contains either \lfloor|E(G)|/k\rfloor or \lceil|E(G)|/k\rceil edges. McDiarmid [ 16 ] observed the following result that we will find useful. Theorem 7 . Let G be a multigraph with chromatic index \chi^{\prime}(G) . Then for all k\geq\chi^{\prime}(G) , there is an equalized edge-coloring of G with k colors. We will also need the following results of Shan [ 19 ] and Plantholt and Shan [ 18 ] . Lemma 8 (Shan [ 19 , Lemma 3.2] ) . There exists a positive integer n_{0} such that for all n\geq n_{0} the following holds. Let G be a graph on 2n vertices, and N=\{x_{1},y_{1},\ldots,x_{t},y_{t}\}\subseteq V(G) , where 1\leq t\leq n is an integer. Then V(G) can be partitioned into two parts A and B satisfying the properties below: (i) |A|=|B| ; (ii) |A\cap\{x_{i},y_{i}\}|=1 for each i\in\{1,\ldots,t\} ; (iii) |d_{A}(v)-d_{B}(v)|\leq

Read the complete text