Extremal graphs for disjoint union of vertex-critical graphs

Wenqian Zhang · 2025

Read Extremal graphs for disjoint union of vertex-critical graphs by Wenqian Zhang (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-2502-15456.txt.

Introduction

Wenqian Zhang, writing alone in two thousand twenty-five, characterizes extremal graphs that avoid a disjoint union of vertex-critical graphs. A vertex-critical graph drops its chromatic number when some vertex is deleted, like an odd wheel.

For a forbidden graph F, the extremal family EX collects the F-free graphs on n vertices with the most edges. Take several vertex-critical graphs sharing one chromatic number and forbid their disjoint union. When the graphs admit a proper ordering, Zhang determines the extremal graphs exactly. The result settles a conjecture by Xiao and Zamora about the extremal problem for disjoint unions of odd wheels, a concrete case of the general theorem.

Catalog record

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

Source: https://arxiv.org/abs/2502-15456

Browse the full library · About the Tower of Babel

Full text

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

Extremal graphs for disjoint union of vertex-critical graphs Wenqian Zhang Abstract For a graph F F , let EX ⁡ ( n , F ) {\rm EX}(n,F) be the set of F F -free graphs of order n n with the maximum number of edges. The graph F F is called vertex-critical, if the deletion of its some vertex induces a graph with smaller chromatic number. For example, an odd wheel (obtained by connecting a vertex to a cycle of even length) is a vertex-critical graph with chromatic number 3. For h ≥ 2 h\geq 2 , let F 1 , F 2 , … , F h F_{1},F_{2},...,F_{h} be vertex-critical graphs with the same chromatic number. Let ∪ 1 ≤ i ≤ h F i \cup_{1\leq i\leq h}F_{i} be the disjoint union of them. In this paper, we characterize the graphs in EX ( n , ∪ 1 ≤ i ≤ h F i ) {\rm EX}(n,\cup_{1\leq i\leq h}F_{i}) , when there is a proper order among the graphs F 1 , F 2 , … , F h F_{1},F_{2},...,F_{h} . This solves a conjecture (on extremal problem for disjoint union of odd wheels) proposed by Xiao and Zamora [ 16 ] . Keywords: extremal graph; disjoint union of wheels; edge-critical graph; vertex-critical graph. 2020 Mathematics Subject Classification: 05C35. † † footnotetext: E-mails: [email protected] 1 Introduction All graphs considered in this paper are finite, undirected and without multi-edges or loops. For a graph G , let \chi(G) denote its chromatic number . The vertex set and edge set of G are denoted by V(G) and E(G) , respectively. Let |G|=|V(G)| and e(G)=|E(G)| . For a subset S\subseteq V(G) , let G[S] be the subgraph of G induced by S , and let G-S=G[V(G)-S] . For a vertex u , denote G-\left\{u\right\} by G-u . Another vertex v is called a neighbor of u , if they are adjacent in G . Let N_{G}(u) be the set of neighbors of u in G , and let N_{S}(u)=S\cap N_{G}(u) . Let d_{G}(u)=|N_{G}(u)| and d_{S}(u)=|N_{S}(u)| . Let \delta(G) denote the minimum degree of G . For any terminology used but not defined here, one may refer to [ 1 ] . Assume that G_{1},G_{2},...,G_{\ell} are \ell\geq 2 graphs. Let \cup_{1\leq i\leq\ell}G_{i} be the disjoint union of them, and let \prod_{1\leq i\leq\ell}G_{i} be the graph obtained from \cup_{1\leq i\leq\ell}G_{i} by connecting each vertex in G_{i} to each vertex in G_{j} for any 1\leq i\neq j\leq\ell . For a positive integer t and a graph H , let tH=\cup_{1\leq i\leq\ell}H . For a certain integer n , let K_{n},C_{n} and P_{n} denote the complete graph, the cycle and the path of order n , respectively. For r\geq 2 , let K_{n_{1},n_{2},...,n_{r}} denote the complete r -partite graph with parts of sizes n_{1},n_{2},...,n_{r} . Let T(n,r) denote the Turán graph of order n with r parts (i.e., the complete r -partite graph of order n with balanced parts). Let F be a graph. For a graph G , denote by F\subseteq G if G contains a copy of F , and by F\nsubseteq G otherwise. G is call F -free, if F\nsubseteq G . Let {\rm EX}(n,F) be the set of F -extremal graphs (i.e., the F -free graphs of order n with the maximum number of edges). Let {\rm ex}(n,F) be the number of edges of any graph in {\rm EX}(n,F) . The classical Turán Theorem [ 15 ] states that {\rm EX}(n,K_{r+1})=\left\{T(n,r)\right\} . Erdős, Stone and Simonovits [ 7 , 8 ] proposed the stability theorem {\rm ex}(n,F)=(1-\frac{1}{\chi(F)-1})\frac{n^{2}}{2}+o(n^{2}). The Turán type problem has attracted many researchers (for example, see [ 2 , 4 , 6 , 10 , 11 , 12 , 17 , 18 , 19 , 20 ] ). A graph F is called edge-critical if there is an edge e of F such that \chi(F-e)=\chi(F)-1 , where F-e denotes the graph obtained from F by deleting the edge e . A graph F is called vertex-critical if there is a vertex u of F such that \chi(F-u)=\chi(F)-1 . Clearly, an edge-critical graph must be vertex-critical. A wheel W_{n} is defined as W_{n}=K_{1}\prod C_{n-1} . W_{n} is called an odd wheel if n is odd, and an even wheel otherwise. Clearly, wheels are vertex-critical graphs, and even wheels are edge-critical graphs. For even wheels, Dzido [ 3 ] proved {\rm ex}(n,W_{2k})=\lfloor\frac{n^{2}}{3}\rfloor for k\geq 3 and n\geq 6k-10 . For odd wheels, Dzido and Jastrzȩbski [ 4 ] determined {\rm ex}(n,W_{5}) and {\rm ex}(n,W_{7}) for all values of n . Recently, Yuan [ 18 ] determined {\rm ex}(n,W_{2k+1}) for k\geq 3 and sufficiently large n . A nearly k -regular graph is a graph of which all vertices have degree k except one vertex with degree k-1 . Let \mathcal{U}^{k-1}_{n}(P_{2k-1}) be the set of P_{2k-1} -free, (k-1) -regular or nearly (k-1) -regular graphs of order n . Let \mathcal{K}_{n_{1},n_{2}}(\mathcal{U}^{k-1}_{n_{1}}(P_{2k-1});P_{2}) be the set of graphs obtained from K_{n_{1},n_{2}} by embedding a graph from \mathcal{U}^{k-1}_{n_{1}}(P_{2k-1}) in the part of size n_{1} , and embedding an edge in the part of size n_{2} . Theorem 1.1 (Yuan [ 18 ] ) For k\geq 3 and sufficiently large n , {\rm ex}(n,W_{2k+1})=\max_{1\leq n_{0}\leq n}\left\{n_{0}(n-n_{0})+\left\lfloor\frac{k-1}{2}n_{0}\right\rfloor+1\right\}. Moreover, {\rm EX}(n,W_{2k+1})\subseteq\mathcal{K}_{n_{0},n-n_{0}}(\mathcal{U}^{k-1}_{n_{0}}(P_{2k-1});P_{2}) . The extremal problem for disjoint union of graphs has been paid attention (for example, see ( [ 9 , 13 , 16 , 17 ] )). In particular, Xiao and Zamora [ 16 ] studied the Turán number of disjoint union of wheels. Since even wheels are edge-critical, for large n , the Turán number of disjoint union of even wheels can be easily determined by a result of Simonovits [ 14 ] . For the disjoint union of odd wheels, they obtained the following result. Theorem 1.2 (Xiao and Zamora [ 16 ] ) For k\geq 3,m\geq 2 and sufficiently large n , \displaystyle\rm{\displaystyle ex}(n,mW_{2k+1}) \displaystyle=\max_{1\leq n_{0}\leq n}\left\{\tbinom{m-1}{2}+\left\lfloor\frac{k-1}{2}n_{0}\right\rfloor+(n_{0}+m-1)(n-m+1)-n^{2}_{0}+1\right\} \displaystyle=\tbinom{m-1}{2}+(m-1)(n-m+1)+{\rm ex}(n-m+1,W_{2k+1}). Moreover, each graph in {\rm EX}(n,mW_{2k+1}) is of form K_{m-1}\prod H , where H\in\mathcal{K}_{n_{0},n-m+1-n_{0}}(\mathcal{U}^{k-1}_{n_{0}}(P_{2k-1});P_{2}). For the disjoint union of distinct odd wheels, Xiao and Zamora [ 16 ] proposed the following conjecture (which follows from Theorem 1.3 ). Conjecture 1 (Xiao and Zamora [ 16 ] ) Assume that k_{1}\geq k_{2}\geq\cdots\geq k_{m} . For sufficiently large n , \displaystyle\rm{\displaystyle ex}(n,\cup_{1\leq i\leq m}W_{2k_{i}+1}) \displaystyle=\max_{1\leq i\leq m,1\leq n_{0}\leq n}\left\{n_{0}(n-n_{0})+(i-1)(n_{0}-i+1)+\tbinom{i-1}{2}+\left\lfloor\frac{k_{i}-1}{2}(n_{0}-i+1)\right\rfloor+1\right\} \displaystyle=\max_{1\leq i\leq m}\left\{\tbinom{i-1}{2}+(i-1)(n-i+1)+{\rm ex}(n-i+1,W_{2k_{i}+1})\right\}. Let F_{1},F_{2},...,F_{h} be h\geq 1 graphs with \chi(F_{i})=r+1\geq 3 for any 1\leq i\leq h . We say that F_{1},F_{2},...,F_{h} is properly ordered, if for any 1\leq\ell\leq h , there exists at least one graph in {\rm EX}(n,F_{\ell}) which contains no copy of any F_{j} with 1\leq j\leq\ell . The main result of this paper is the following theorem. Theorem 1.3 For h\geq 2 , let F_{1},F_{2},...,F_{h} be properly ordered vertex-critical graphs with \chi(F_{i})=r+1\geq 3 for any 1\leq i\leq h . Then, for sufficiently large n , {\rm ex}(n,\cup_{1\leq i\leq h}F_{i})=\max_{1\leq\ell\leq h}\left\{\tbinom{\ell-1}{2}+(\ell-1)(n-\ell+1)+{\rm ex}(n-\ell+1,F_{\ell})\right\}. Moreover, each graph in {\rm EX}(n,\cup_{1\leq i\leq h}F_{i}) is of form K_{\ell-1}\prod H , where H\in{\rm EX}(n-\ell+1,F_{\ell}) . For any k\geq 2 and sufficiently large n , from Theorem 1.1 we see that each graph in {\rm EX}(n,W_{2k+1}) contains no copy of any W_{2\ell+1} with \ell\geq k . Thus, W_{2k_{1}+1},W_{2k_{2}+1},...,W_{2k_{h}+1} is properly ordered if

Read the complete text