On the Hilton-Zhao vertex-splitting conjecture
2026
Read On the Hilton-Zhao vertex-splitting conjecture (2026) 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-2605-18783.txt.
Introduction
Xuli Qi and Yanrui Feng settle a 1997 conjecture about splitting a vertex in a regular graph. Hilton and Zhao had claimed that splitting one vertex in a connected regular Class 1 graph yields an edge-critical graph when the degree tops one third of the vertex count. Earlier work had reached only three quarters of that count. Qi and Feng push the proof down to a threshold just below two thirds, closing the gap for high-degree graphs.
Catalog record
| YEAR | 2026 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32201 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.18783
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Hilton-Zhao vertex-splitting conjecture Abstract Let G G be a simple graph with order n n , maximum degree Δ ( G ) \Delta(G) , and chromatic index χ ′ ( G ) \chi^{\prime}(G) , respectively. A graph G G is edge-chromatic critical if χ ′ ( H ) < χ ′ ( G ) \chi^{\prime}(H)<\chi^{\prime}(G) for every proper subgraph H H of G G . Assume that G G is an n n -vertex connected regular Class 1 1 graph, and let G ∗ G^{*} be obtained from G G by splitting one vertex into two vertices. Hilton and Zhao in 1997 proposed the vertex-splitting conjecture: if Δ ( G ) > n 3 \Delta(G)\textgreater\frac{n}{3} , then G ∗ G^{*} is edge-chromatic critical. Recently, Cao, Chen, and Shan (Discrete Math. 2022) verified the conjecture for Δ ( G ) ≥ 3 n 4 \Delta(G)\geq\frac{3n}{4} . In this paper, we confirm the conjecture for Δ ( G ) ≥ 2 n − 2 3 \Delta(G)\geq\frac{2n-2}{3} . Keywords: edge coloring, vertex-splitting conjecture, multi-fan, Kierstead path Xuli Qi ∗ , Yanrui Feng Department of Mathematics, Hebei University of Science and Technology, Shijiazhuang 050018, P.R. China * * footnotetext: Corresponding author. E-mail addresses: [email protected] (X. Qi); [email protected] (Y. Feng) 1 Introduction We consider simple connected graphs and generally follow the book [ 8 ] of Stiebitz et al. for notation and terminology. Let G be a graph, and V(G) and E(G) be the vertex set and the edge set of G , respectively. A graph G is \Delta -regular if \delta(G)=\Delta(G)=\Delta , where \delta(G) and \Delta(G) are respectively the minimum degree and maximum degree of G . Let [k]:=\{1,\dots,k\} , that is, the set of the first k consecutive positive integers. A k -edge-coloring of a graph G is a map \varphi:E(G)\to[k] that assigns to every edge e of G a color \varphi(e)\in[k] such that no two adjacent edges of G receive the same color. Denote by \mathcal{C}^{k}(G) the set of all k -edge-colorings of G . The chromatic index \chi^{\prime}(G) is the least integer k such that \mathcal{C}^{k}(G)\neq\emptyset . In 1960s, Vizing [ 10 ] and, independently, Gupta [ 6 ] proved that \Delta(G)\leq\chi^{\prime}(G)\leq\Delta(G)+1 , which leads to a natural classification of graphs. Following Fiorini and Wilson [ 3 ] , if \chi^{\prime}(G)=\Delta(G) , then G is of Class 1 ; otherwise, it is of Class 2 . Holyer [ 5 ] proved that it is NP-complete to determine whether an arbitrary graph is of Class 1 . We know that \chi^{\prime}(G)\geq\left|E(G)\right|/\lfloor\left|V(G)\right|/2\rfloor since every matching of G has at most \lfloor\left|V(G)\right|/2\rfloor edges. A graph G is overfull if \left|E(G)\right|>\Delta(G)\lfloor\left|V(G)\right|/2\rfloor . Clearly, if G is overfull then \chi^{\prime}(G)=\Delta(G)+1 , and so G is of Class 2 . Easily implied by its definition, overfull graphs have odd order. A graph G is edge-chromatic critical if \chi^{\prime}(H)<\chi^{\prime}(G) for every proper subgraph H of G . In investigating the classification problem, edge-chromatic critical graphs of Class 2 are of particular interest. Furthermore, we call G a \Delta -critical graph if G is edge-chromatic critical and \chi^{\prime}(G)=\Delta+1 , where \Delta:=\Delta(G) . We study sufficient conditions for a Class 2 graph to be edge-chromatic critical. For v\in V(G) , let N_{G}(v) denote the set of neighbors of v in G . A vertex-splitting in a graph G at a vertex v forms a new graph G^{*} : replacing v\in V(G) with two new adjacent vertices v_{1} and v_{2} and partitioning N_{G}(v) into two nonempty subsets that serve as the set of neighbors of v_{1} and v_{2} from V(G) in G^{*} , respectively. We say the new graph G^{*} is obtained from G by a vertex-splitting. Vertex-splitting was called the “Möbius-type gluing technique” in [ 1 ] and [ 9 ] . It is easy to see that a regular Class 1 graph has even order, and that every graph obtained from a regular graph of even order by a vertex-splitting is overfull. Hilton and Zhao [ 4 ] in 1997 proposed the following conjecture. Conjecture 1 (Vertex-splitting conjecture) . Let G be an n -vertex connected \Delta -regular Class 1 graph with \Delta\textgreater\frac{n}{3} . If G^{*} is obtained from G by a vertex-splitting, then G^{*} is \Delta -critical. It is easy to check that the graph G^{*} above is overfull, so it is of Class 2 . Thus the difficulty of vertex-splitting conjecture is to test that G^{*} is edge-chromatic critical. Hilton and Zhao [ 4 ] verified the conjecture for graphs G with \Delta(G)\geq(\sqrt{7}-1)n/2\approx 0.82n . Song [ 7 ] in 2002 verified the conjecture for a class of special graphs G with \Delta(G)\geq 0.5n . Recently, Cao, Chen and Shan [ 2 ] proved the conjecture when \Delta(G)\geq 0.75n . In this paper, we confirm the conjecture for \Delta(G)\geq\frac{2n-2}{3} as follows. Theorem 1 . Let n and \Delta be positive integers such that \Delta\geq\frac{2n-4}{3} . If an n -vertex graph G is obtained from an (n-1) -vertex connected \Delta -regular Class 1 graph by a vertex-splitting, then G is \Delta -critical. 2 Definitions and preliminary results Let G be a graph. For e\in E(G) , G-e represents the graph obtained from G by deleting the edge e . An edge e is a critical edge of G if \chi^{\prime}(G-e)<\chi^{\prime}(G) . Clearly, if G is of Class 2 and every edge is critical, then G is edge-chromatic critical. For u\in V(G) , let d_{G}(u) denote the degree of u in G . The symbol \Delta is reserved for \Delta(G) in this paper. A \Delta -vertex in G is a vertex with maximum degree in G . For u\in V(G) , a \Delta -neighbor of u is a neighbor of u that is a \Delta -vertex in G . When u,v\in V(G) are adjacent, we call (u,v) a full-deficiency pair of G if d_{G}(u)+d_{G}(v)=\Delta+2 . Let G be a graph with an edge e\in E(G) , and an edge coloring \varphi\in\mathcal{C}^{k}(G-e) for some integer k\geq\Delta . For a vertex v\in V(G) , let \varphi(v) denote the set of colors assigned to edges incident with v , and \overline{\varphi}(v)=[k]\setminus\varphi(v) , that is, the set of colors not assigned to any edge incident with v . We call \varphi(v) the set of colors present at v and \overline{\varphi}(v) the set of colors missing at v . Clearly, |\varphi(v)|+|\overline{\varphi}(v)|=k for each vertex v\in V(G) . For a vertex set X\subseteq V(G) , we define \overline{\varphi}(X)=\bigcup_{v\in X}\overline{\varphi}(v) . The set X is called elementary with respect to \varphi or simply \varphi -elementary if \overline{\varphi}(u)\cap\overline{\varphi}(v)=\emptyset for any two distinct vertices u,v\in X . For a color \alpha\in[k] , let E_{\varphi,\alpha}(G) denote the set of edges colored with \alpha . Let \alpha,\beta\in[k] be two distinct colors, and H be the spanning subgraph induced by E_{\varphi,\alpha}(G) and E_{\varphi,\beta}(G) . Clearly, every component of H is either a path or an even cycle, each of which is referred to as an (\alpha,\beta) -chain of G . If we swap the colors \alpha and \beta on an (\alpha,\beta) -chain C , then we obtain a new (proper) k -edge-coloring of G , which is also in \mathcal{C}^{k}(G-e) . This operation is called a Kempe change . Furthermore,