Extending total colorings in planar graphs

Owen Henderschedt, Jessica McDonald · 2025

Read Extending total colorings in planar graphs by Owen Henderschedt, Jessica McDonald (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-2509-18940.txt.

Introduction

Owen Henderschedt and Jessica McDonald open a new question in graph coloring: when can part of a coloring be extended to the whole graph? They work with total colorings, where both points and edges get colors and neighbors must differ. Their graphs are planar, meaning they can be drawn flat with no crossing edges. The question is whether a coloring fixed on a small piece can always be completed.

For a starting piece that is a matching, a set of edges with no shared points, they prove extension works with a stated number of colors. That holds once the largest degree is high enough, and the number of colors cannot be lowered in general. For starting pieces made of small tight groups set far apart, extension works with fewer extra colors. There the spacing condition also cannot be relaxed.

Catalog record

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

Source: https://arxiv.org/abs/2509-18940

Browse the full library · About the Tower of Babel

Full text

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

Extending total colorings in planar graphs Owen Henderschedt, Jessica McDonald Abstract We initiate the study of total-coloring extensions, and focus our attention on planar graphs, asking: “When can a total- k k -coloring of some subgraph H H of a planar graph G G be extended to a total- k k -coloring of G G ?” We prove that if H H is a matching, then any total- ( Δ + 3 ) (\Delta+3) -coloring of H H in G G extends to G G provided Δ ≥ 28 \Delta\geq 28 ; this number of colors is best-possible without introducing a distance condition on H H . We also prove that if H H is a set of distance-3 cliques then any total- ( Δ + 1 ) (\Delta+1) -coloring of H H extends to G G provided Δ ≥ 27 \Delta\geq 27 ; this distance condition cannot be lowered. 1 Introduction Once a coloring result is known, it is natural to ask how robust that result is via a coloring extension problem . Namely, if we know that a graph G is k -colorable we may ask: when can a k -coloring of some subgraph H of G be extended to a k -coloring of G ? Extension problems have been studied for both vertex-colorings and edge-colorings, particularly when G is planar. In this paper we initiate the study of total-coloring extension problems. We prove three main results, all of which are for planar graphs, and conjecture a number of generalizations. Our results concern the cases when H is a matching, when H is more generally a disjoint set of cliques, and when H has bounded maximum degree. Each of these results is motivated by work that has been done on vertex-coloring and edge-coloring extension problems, and as well as total and list-total coloring results. In this paper all graphs are simple; we refer the reader to [ 19 ] for terms not defined here. Given a graph G , a total- k -coloring is an assignment of the colors \{1,2,\ldots,k\}=[k] to the vertices and edges of G such that the vertices induce a k -coloring, the edges induce a k -edge-coloring, and no edge can receive the same color as either of its endpoints. The total chromatic number of a graph G , denoted \chi_{T}(G) , is the smallest k such that there exists a total- k -coloring of G . By considering the edges incident with a vertex of maximum degree \Delta(G) , along with the vertex itself, we see that \chi_{T}(G)\geq\Delta(G)+1 . In the 1960’s, Behzad [ 4 ] and Vizing [ 18 ] independently proposed the Total Coloring Conjecture which says that \chi_{T}(G) is at most one more than this lower bound. Conjecture 1.1 (The Total Coloring Conjecture) . For any graph G , \chi_{T}(G)\leq\Delta(G)+2 . Conjecture 1.1 has been verified for all planar graphs G with \Delta(G)\neq 6 through a series of papers (see [ 13 , 16 ] ). In fact, it is known that \chi_{T}(G)=\Delta(G)+1 for planar graphs with \Delta(G)\geq 9 (see [ 14 ] ), although this is false when \Delta(G)\leq 3 . For much more on the Total Coloring Conjecture, both in the planar case and in general, the interested reader is referred to [ 8 ] and [ 12 ] . Suppose we have a graph G with a subgraph H and \varphi is a total- k -coloring of H . We want to know whether \varphi can be extended to G , that is, whether there exists a total- k -coloring of G which agrees with \varphi on all the vertices and edges of H . Of course, if there are vertices u and v which are adjacent in G but non-adjacent in H and moreover \varphi(u)=\varphi(v) , then we cannot hope to extend \varphi to G . We say that \varphi is a total- k -coloring of H in G if no such vertices u,v exist, that is, if the coloring \varphi is proper also with respect to G . In general, if \varphi is a total- k -coloring of H in G , then any uncolored vertex in G sees at most 2\Delta(G) colors from \varphi (all adjacent vertices and incident edges) and any uncolored edge in G sees at most 2\Delta(G) colors ( 2\Delta(G)-2 adjacent edges and 2 endpoints). So we get the following basic observation by coloring greedily. Observation 1 . If G is a graph with maximum degree \Delta and H is a subgraph of G , then any total- (2\Delta+1) -coloring of H in G can be extended to G . Without putting any restrictions on H , the (2\Delta+1) in Observation 1 is best possible due to Example 1 (given in Section 2). So we must make restrictions on the precolored subgraph H if we want to lower the number of colors beyond the (2\Delta+1) , and certainly if we want to approach the (\Delta+2) suggested by the Total Coloring Conjecture. Our starting point for this is matchings. While a matching is typically defined as a set of edges within a graph whose endpoints are vertex disjoint, we extend this notion here and say that a subgraph H of a graph G is a matching if it induces a set of matching edges in H , i.e., if H consists of vertex-disjoint copies of K_{2} within G . Conjecture 1.2 . Let G be a graph with maximum degree \Delta and let H be a subgraph of G . If H is a matching, then any total- (\Delta+3) -coloring of H in G can be extended to G . Theorem 1.3 . Let G be a planar graph with maximum degree \Delta\geq 28 and let H be a subgraph of G . If H is a matching, then any total- (\Delta+3) -coloring of H in G can be extended to G . The (\Delta+3) in 1.2 and Theorem 1.3 (the first main result of this paper), is best possible due to Example 2 (given in Section 2). In fact, this example shows that (\Delta+3) cannot even be replaced by (\chi_{T}(G)+1) . Given a graph G with a subgraph H that is a matching, we say that H is distance- \ell if the distance between any two vertices in distinct components of H is at least \ell in G . The matching in Example 2 is distance-2, and we conjecture that this distance is the barrier for extending from totally- (\Delta+2) -colored matchings. Conjecture 1.4 . Let G be a graph with maximum degree \Delta and let H be a subgraph of G . If H is a distance-3 matching, then any total- (\Delta+2) -coloring of H can be extended to G . While we can’t hope for fewer than \Delta+2 colors in general, we can actually do better than Conjecture 1.4 in the planar case when the maximum degree is large enough. Theorem 1.5 . Let G be a planar graph with maximum degree \Delta\geq 27 and let H be a subgraph of G . If H is a distance-3 matching, then any total- (\Delta+1) -coloring of H can be extended to G . Note that we do not need to

Read the complete text