betaFeedback

WorksMathematics

Hilton-Zhao vertex-splitting conjecture for triangle-free graphs

Abstract

Every graph obtained from a regular Class 11 graph by a vertex-splitting is overfull and hence is of Class 22; the central question is whether the resulting graph is edge-chromatic critical. We consider a revised version of the Hilton-Zhao vertex-splitting conjecture for triangle-free base graphs, excluding the known cubic exception that arises from the Wagner graph. Let GG be a connected nn-vertex triangle-free ΔΔ-regular Class 11 graph, and let G∗G^{*} be obtained from GG by splitting one vertex into two adjacent vertices. We first show that any non-extreme vertex-splitting produces a ΔΔ-critical graph provided Δ>n−13Δ>\frac{n-1}{3}. Consequently, for non-extreme vertex-splittings, the revised version of the conjecture is valid across its entire conjectured degree range, and indeed even under a slightly weaker degree condition. We next turn to arbitrary vertex-splittings, extreme ones included. It is shown that G∗G^* is ΔΔ-critical provided n≥10n \ge 10 and Δ>2n−35Δ>\frac{2n-3}{5}. In addition, for n>24n>24, the non-strict condition Δ≥2n−35Δ\ge \frac{2n-3}{5} is already sufficient. This extends the bipartite range Δ>2n5Δ>\frac{2n}{5} to the boundary range that the bipartite argument does not cover. In particular, our arguments give a complete treatment of the case of triangle-free 66-regular base graphs in the conjectured range. The proofs bring together structural properties of full-deficiency pairs, homomorphism theorems for dense triangle-free graphs, and Hamilton decompositions built via graph detachment.

Introduction

Unless otherwise stated, we consider simple connected graphs in this paper. Nevertheless, in Lemmas 2.8 and 4.4, we consider multigraphs, which are defined as graphs allowing parallel edges and loops. For general notation and terminology, we follow the book [17] of Stiebitz et al.; the specific conventions for multigraphs are detailed later. Let G=(V(G),E(G))G=(V(G),E(G)) be a graph, where V(G)V(G) is the vertex set and E(G)E(G) is the edge set of GG. Two graphs GG and HH are isomorphic, denoted by G≅HG\cong H, if there exists a bijection f:V(G)→V(H)f:V(G)\to V(H) such that uv∈E(G)uv\in E(G) if and only if f(u)f(v)∈E(H)f(u)f(v)\in E(H). Let Z\mathbb{Z} denote the set of integers. For two integers ss and tt, let [s,t]:={i∈Z:s≤i≤t}[s,t]:=\{i\in\mathbb{Z}:s\le i\le t\}.

For u,v∈V(G)u,v\in V(G), let dist⁡G(u,v)\operatorname{dist}_G(u,v) be the length of a shortest path between uu and vv in GG. For a vertex u∈V(G)u\in V(G) and a subset S⊆V(G)S\subseteq V(G), define dist⁡G(u,S):=min⁡s∈Sdist⁡G(u,s)\operatorname{dist}_G(u,S):=\min_{s\in S}\operatorname{dist}_G(u,s). We also define NG(u):={v∈V(G):dist⁡G(u,v)=1}N_G(u):=\{v\in V(G):\operatorname{dist}_G(u,v)=1\}, dG(u):=∣NG(u)∣d_G(u):=|N_G(u)|, and NG[u]:=NG(u)∪{u}N_G[u]:=N_G(u)\cup\{u\}. Here dG(u)d_G(u) is the degree of uu, NG(u)N_G(u) is its open neighborhood, and NG[u]N_G[u] is its closed neighborhood. Denote by Δ(G)\Delta(G) and δ(G)\delta(G) (or simply Δ\Delta and δ\delta) respectively the maximum degree and minimum degree of graph GG. A graph GG is called Δ\Delta-regular if all vertices of GG have the same degree Δ\Delta, that is, Δ(G)=δ(G)=Δ\Delta(G)=\delta(G)=\Delta.

A proper kk-edge-coloring of GG is a map φ:E(G)→[1,k]\varphi:E(G)\to[1,k] that assigns to every edge ee of GG a color φ(e)∈[1,k]\varphi(e)\in[1,k] such that no two adjacent edges of GG receive the same color. Let Ck(G)C^k(G) denote the collection of all proper kk-edge-colorings of GG. The chromatic index χ′(G)\chi'(G) is the least integer kk such that Ck(G)≠∅C^k(G)\ne\varnothing. By the celebrated results of Vizing [19] and Gupta [10], every simple graph satisfies Δ(G)≤χ′(G)≤Δ(G)+1\Delta(G)\le\chi'(G)\le\Delta(G)+1. Following Fiorini and Wilson [9], GG is of Class 1 if χ′(G)=Δ(G)\chi'(G)=\Delta(G); otherwise, it is of Class 2. Determining whether an arbitrary graph belongs to Class 1 is computationally difficult; Holyer [13] proved that this decision problem is NP-complete. We know that each color class in a proper edge-coloring is a matching and therefore contains at most ⌊∣V(G)∣/2⌋\lfloor|V(G)|/2\rfloor edges. Consequently, χ′(G)≥∣E(G)∣/⌊∣V(G)∣/2⌋\chi'(G)\ge|E(G)|/\lfloor|V(G)|/2\rfloor. We say that GG is overfull if ∣E(G)∣>Δ(G)⌊∣V(G)∣/2⌋|E(G)|>\Delta(G)\lfloor|V(G)|/2\rfloor. Hence, an overfull simple graph has chromatic index Δ(G)+1\Delta(G)+1 and is therefore of Class 2. Notice also that an overfull graph necessarily has odd order.

A graph GG is called edge-chromatic critical if χ′(H)<χ′(G)\chi'(H)<\chi'(G) for every proper subgraph HH of GG. In particular, if GG is edge-chromatic critical and χ′(G)=Δ(G)+1\chi'(G)=\Delta(G)+1, then GG is called a Δ\Delta-critical graph, where Δ:=Δ(G)\Delta:=\Delta(G). In this paper, we are concerned with sufficient conditions for a Class 2 graph to be edge-chromatic critical. Let GG be a graph and e∈E(G)e\in E(G). We write G−eG-e for the graph obtained from GG by deleting the edge ee. An edge ee is called a critical edge if χ′(G−e)<χ′(G)\chi'(G-e)<\chi'(G). Thus, a Class 2 graph is edge-chromatic critical precisely when every edge is critical. A vertex-splitting in a graph GG at a vertex vv forms a new graph G∗G^*: replacing v∈V(G)v\in V(G) with two new adjacent vertices v1v_1 and v2v_2 and partitioning NG(v)N_G(v) into two nonempty subsets that serve as the set of neighbors of v1v_1 and v2v_2 from V(G)V(G) in G∗G^*, respectively. We say the new graph G∗G^* is obtained from GG by a vertex-splitting. We call this vertex-splitting extreme if max⁡{dG∗(v1),dG∗(v2)}=Δ(G)\max\{d_{G^*}(v_1),d_{G^*}(v_2)\}=\Delta(G). Otherwise, we call it non-extreme; that is, dG∗(v1)<Δ(G)d_{G^*}(v_1)<\Delta(G) and dG∗(v2)<Δ(G)d_{G^*}(v_2)<\Delta(G). Vertex-splitting was called the “Möbius-type gluing technique” in [4, 18]. It is easy to check 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.

Let Γ\Gamma (see Figure 1) denote the Wagner graph, i.e., eight-vertex Möbius ladder with V(Γ)={x0,…,x7}V(\Gamma)=\{x_0,\ldots,x_7\} and NΓ(xi)={xi−1,xi+1,xi+4}N_{\Gamma}(x_i)=\{x_{i-1},x_{i+1},x_{i+4}\}, where the subscripts are taken modulo 8. Splitting a vertex does not always produce an edge-chromatic critical graph. As noted in [12, 20], the graph obtained from the Wagner graph Γ\Gamma by subdividing one of its four opposite chords {x0x4,x1x5,x2x6,x3x7}\{x_0x_4,x_1x_5,x_2x_6,x_3x_7\} is not edge-chromatic critical. Therefore, excluding the known cubic exception mentioned above, we consider a revised version of the Hilton-Zhao conjecture [12] as follows.

Wagner graph $\Gamma$

Figure 1. Wagner graph Γ\Gamma

Conjecture 1 (Vertex-splitting conjecture). Let GG be an nn-vertex Δ\Delta-regular Class 1 graph satisfying Δ>n3\Delta> \frac{n}{3}, and let G∗G^* be obtained from GG by a vertex-splitting. If G∗G^* is not isomorphic to the graph obtained from the Wagner graph Γ\Gamma by subdividing one of its four opposite chords, then G∗G^* is Δ\Delta-critical.

Since any graph obtained from a regular Class 1 graph by a vertex-splitting is overfull and hence is of Class 2, the central question is whether the resulting graph is edge-chromatic critical. Some additional small-degree cases are covered by the classifications of small-order critical graphs in [3, 6, 8]. Several partial results have been obtained. Hilton and Zhao [12] proved the conjecture for graphs GG satisfying Δ(G)≥7−12n+2≈0.82n\Delta(G) \ge\frac{\sqrt{7}-1}{2}n+2 \approx0.82n. In 2002, Song [16] verified the conjecture for non-extreme vertex-splittings when diameter at most two, in particular when Δ(G)≥0.5n\Delta(G) \ge0.5n. In 2022, Cao, Chen, and Shan [7] verified the conjecture under the condition Δ(G)≥0.75n\Delta(G) \ge0.75n. Recently, Qi and Feng [15] proved the conjecture for Δ(G)≥2n−23\Delta(G) \ge\frac{2n-2}{3}.

In this paper, we consider a revised version of the Hilton-Zhao vertex-splitting conjecture for triangle-free base graphs. Let GG be an nn-vertex triangle-free Δ\Delta-regular Class 1 graph, and let G∗G^* be obtained from GG by a vertex-splitting. Our first result shows that, for non-extreme vertex-splittings, the revised version of the conjecture is valid across its entire conjectured degree range, and indeed even under a slightly weaker degree condition. We also give a complete treatment of triangle-free 6-regular base graphs in the conjectured range. Finally, for arbitrary vertex-splittings, extreme ones included, we extend the bipartite range Δ>2n5\Delta> \frac{2n}{5} to the boundary range that the bipartite argument does not cover. The precise statements of our four main results are given below.

Theorem 1.1. Let GG be an nn-vertex triangle-free Δ\Delta-regular Class 1 graph with Δ(G)>n−13\Delta(G) > \frac{n-1}{3} and G∗G^* be obtained from GG by splitting a vertex vv into two adjacent vertices aa and bb. If dG∗(a)<Δ(G)d_{G^*}(a) < \Delta(G) and dG∗(b)<Δ(G)d_{G^*}(b) < \Delta(G), then G∗G^* is Δ\Delta-critical.

Theorem 1.2. Let GG be an nn-vertex triangle-free 6-regular Class 1 graph. If 6>n36 > \frac{n}{3}, then every graph obtained from GG by a vertex-splitting is 6-critical.

Theorem 1.3. Let GG be an nn-vertex triangle-free Δ\Delta-regular Class 1 graph. If Δ(G)≥2n−35\Delta(G) \ge\frac{2n-3}{5} with n>24n > 24, then every graph obtained from GG by a vertex-splitting is Δ\Delta-critical.

Theorem 1.4. Let GG be an nn-vertex triangle-free Δ\Delta-regular Class 1 graph. If Δ(G)>2n−35\Delta(G) > \frac{2n-3}{5} with n≥10n \ge10, then every graph obtained from GG by a vertex-splitting is Δ\Delta-critical.

The remainder of this paper is structured as follows. In § 2, we introduce the terminology and notation and collect the preliminary results. In § 3, we prove Theorem 1.1, which concerns non-extreme vertex-splittings. § 4 is dedicated to developing the auxiliary results for extreme vertex-splittings. In § 6, we prove Theorem 1.2, while § 7 is devoted to the proofs of Theorems 1.3 and 1.4.

Definitions and preliminary results

References

  1. [1]B. Andrásfai, P. Erdős, V.T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218.DOI
  2. [2]M.A. Bahmanian, C.A. Rodger, Multiply balanced edge colorings of multigraphs, J. Graph Theory 70 (3) (2012), 297–317.DOI
  3. [3]D. Bokal, G. Brinkmann, S. Grünewald, Chromatic-index-critical graphs of orders 13 and 14, Discrete Math. 300 (2005), 16–29.DOI
  4. [4]S. Bonvicini, A. Vietri, A Möbius-type gluing technique for obtaining edge-critical graphs, Ars Math. Contemp. 19 (2) (2020), 209–229.DOI
  5. [5]S. Brandt, On the structure of dense triangle-free graphs, Combin. Probab. Comput. 8 (3) (1999), 237–245.DOI
  6. [6]G. Brinkmann, E. Steffen, Chromatic-index-critical graphs of orders 11 and 12, Europ. J. Combin. 19 (8) (1998), 889–900.DOI
  7. [7]Y. Cao, G. Chen, S. Shan, An improvement to the Hilton-Zhao vertex-splitting conjecture, Discrete Math. 345 (2022), 112902.DOI
  8. [8]A.G. Chetwynd, H.P. Yap, Chromatic index critical graphs of order 9, Discrete Math. 47 (1983), 23–33.DOI
  9. [9]S. Fiorini, R.J. Wilson, Edge-Colourings of Graphs, Research Notes in Maths., Pitman, London, 1977.
  10. [10]R.P. Gupta, Studies in the Theory of Graphs, PhD thesis, Tata Institute of Fundamental Research, Bombay, 1967.
  11. [11]R. Häggkvist, Odd cycles of specified length in non-bipartite graphs, in: B. Bollobás (Ed.), Graph Theory: Proceedings of the Conference on Graph Theory, Cambridge, North-Holland Math. Stud., vol. 62, North-Holland, Amsterdam, 1982, pp. 89–99.DOI
  12. [12]A.J.W. Hilton, C. Zhao, Vertex-splitting and chromatic index critical graphs, Discrete Appl. Math. 76 (1997), 205–211.DOI
  13. [13]I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (4) (1981), 718–720.DOI
  14. [14]W. Mantel, Problem 28, Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W.A. Wythoff, Wisk. Opgaven 10 (1907), 60–61.
  15. [15]X. Qi, Y. Feng, On the Hilton-Zhao vertex-splitting conjecture, Discrete Math. 349 (2026), 115341.
  16. [16]Z.-X. Song, A further extension of Yap’s construction for Δ-critical graphs, Discrete Math. 243 (2002), 283–290.DOI
  17. [17]M. Stiebitz, D. Scheide, B. Toft, L.M. Favrholdt, Graph Edge Coloring: Vizing’s Theorem and Goldberg’s Conjecture, Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2012.
  18. [18]A. Vietri, An analogy between edge colourings and differentiable manifolds, with a new perspective on 3-critical graphs, Graphs Combin. 31 (6) (2015), 2425–2435.DOI
  19. [19]V.G. Vizing, Critical graphs with given chromatic class, Diskret. Analiz. 5 (1965), 9–17.
  20. [20]H.P. Yap, A construction of chromatic index critical graphs, J. Graph Theory 5 (1981), 159–163.DOI

Paper details

vlnc:W_fhq4ahgg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents