Proof. Let $G$ be an $n$ -vertex graph and $\delta (G) \geq \left (\frac {1}{2} + \gamma \right )n.$ By subdividing one edge of $H^*$ at most $v(H^*)$ more times, we obtain a graph $F$ with a constant number of vertices, $\chi (F) \leq 3$ , and $v(G) - v(F)$ is divisible by $v(H^*)$ . By the Erdős–Stone–Simonovits theorem, we can find a copy of $F$ in $G.$ Since $v(F)$ is bounded, the minimum degree of $G[V(G)\setminus V(F)]$ is greater than $\left (\frac {1}{2} + \frac {\gamma }{2}\right )n$ for $n \geq n_0$ , where $n_0$ depends only on $H.$ Then by Theorem1.2, there is a perfect $H^*$ -tiling in $G[V(G)\setminus V(F)]$ which yields a perfect $H$ -subdivision tiling in $G$ together with the copy of $F.$ This completes the proof.

Proof. We may assume $|A| \leq |B|.$ It suffices to show that $\xi (H) \leq \frac {|A| + |B|}{|B|}.$ Let $U$ be the branch vertices of $F$ and let $X = A \cap U$ and $Y = B \cap U.$ Let $p = |X| + e(H[Y])$ and $q = |Y| + e(H[X]).$ Then $f_H(Y) = \frac {p + q}{q}.$ Since $F$ is a bipartite subdivision of $H$ with branch set $X \cup Y$ , every edge in $H[X, Y]$ is subdivided an even number of times. Thus, there is a non-negative integer $c$ such that $\frac {|A| + |B|}{|B|} = \frac {p + q + 2c}{q + c}$ . If $\frac {p + q}{q} \geq 2$ , then $\frac {|A| + |B|}{|B|} \geq 2.$ Since $\xi (H) \leq 2$ , in this case, the observation is proved. Otherwise, we may observe that $p \lt q.$ Then $\frac {|A| + |B|}{|B|} = \frac {p + q + 2c}{q + c} \geq \frac {p + q}{q}$ holds. By the definition of $\xi (H)$ , we have $\xi (H) \leq H(Y) = \frac {p + q}{q}.$ This completes the proof.

Proof. Let $G$ be an $n$ -vertex complete bipartite graph with bipartition $X$ and $Y$ such that $|X| \leq |Y|$ . Note that as $G$ is a bipartite graph, every subdivision of $H$ in $G$ is bipartite. By Observation3.2, if $\frac {|Y|}{|X|} \gt \frac {1}{\xi (H) - 1}$ , then $G$ does not have a perfect $H$ -subdivision tiling. Let $|X| = \left \lfloor \left (1 - \frac {1}{\xi (H)} \right )n \right \rfloor - 1$ . Then $\delta (G) = \left \lfloor \left (1 - \frac {1}{\xi (H)} \right )n \right \rfloor - 1$ and $\frac {|Y|}{|X|} \gt \frac {1}{\xi (H) - 1}$ . Thus, $G$ does not have a perfect $H$ -subdivision tiling.

Proof of Claim 1. Let $A^{\prime}$ and $B^{\prime}$ be the branch vertices of $H$ contained in $A$ and $B$ , respectively. Let $uv\in E(H)$ be an edge and let $u z_1, \ldots , z_k, v$ be the subdivided path in $H^{\prime}$ that corresponds to $uv$ . If $u\in A$ and $v\in B$ , then $k$ is an even number since $H^{\prime}$ is a bipartite graph. Thus, we observe that $|B\cap \{z_1,\ldots , z_k\}| - |A\cap \{z_1, \ldots , z_k\}| = 0$ . If both $u$ and $v$ are in $A$ , the number $k$ is odd and the equality $|B\cap \{z_1,\ldots , z_k\}| - |A\cap \{z_1, \ldots , z_k\}| = 1$ holds since $H^{\prime}$ is a bipartite graph. Similarly, if both $u$ and $v$ are in $B$ , then we have $|B\cap \{z_1,\ldots , z_k\}| - |A\cap \{z_1, \ldots , z_k\}| = -1$ . Hence, we have the following.

\begin{align*}|B| - |A| = e(H[A^{\prime}]) - e(H[B^{\prime}]) + |B^{\prime}| - |A^{\prime}| = (|B^{\prime}| + e(H[A^{\prime}])) - (|A^{\prime}| + e(H[B^{\prime}])).\end{align*}

Thus, by the definition of $\mathrm {hcf}_{\xi }(H)$ , the number $|B| - |A|$ is divisible by $\mathrm {hcf}_{\xi }(H)$ . This completes the proof.

Proof of Proposition 3.4. Let $F\in \mathrm {Sub}(H)$ be a bipartite graph with bipartition $A$ and $B$ . Since $F$ is a bipartite subdivision of $H$ , by Claim1, the difference $|B| - |A|$ is divisible by $\mathrm {hcf}_{\xi }(H)$ . If $G$ is a bipartite graph, and the difference between the sizes of two bipartitions of $G$ is not divisible by $\mathrm {hcf}_{\xi }(H)$ , the graph $G$ does not have a perfect $H$ -subdivision tiling since every subdivision of $H$ in $G$ is bipartite.

First, let $n$ be an even number and $\mathrm {hcf}_{\xi }(H) \gt 2$ . Let $G = K_{\frac {n}{2} - 1, \frac {n}{2} + 1}$ . Then, the difference between the two bipartitions of $G$ is two which cannot be divisible by $\mathrm {hcf}_{\xi }(H)$ since $\mathrm {hcf}_{\xi }(H) \gt 2$ .

Second, let $n$ be an odd number and $\mathrm {hcf}_{\xi }(H) \neq 1$ . Let $G = K_{\left \lfloor \frac {n}{2} \right \rfloor , \left \lceil \frac {n}{2} \right \rceil }$ . Then, the difference between the sizes of the two bipartitions of $G$ is $1$ , which is not divisible by $\mathrm {hcf}_{\xi }(H)$ as $\mathrm {hcf}_{\xi }(H) \neq 1$ .

Proof. Let $(A, B, C)$ be a partition of $[n]$ with sizes $|A| = \left \lfloor \frac {1}{3}n \right \rfloor - 1$ and $|B| = \left \lfloor \frac {1}{3}n \right \rfloor$ . Let $G$ be a graph on vertex set $[n]$ such that $G$ is a disjoint union of a clique on $C$ and a complete bipartite graph with bipartition $(A, B)$ . Then, the minimum degree of $G$ is $\left \lfloor \frac {1}{3}n \right \rfloor - 1$ . Let $G_1 = G[A \cup B]$ and $G_2 = G[C]$ . Since $G_1$ and $G_2$ are disjoint, if $G$ contains a perfect $H$ -subdivision tiling, so does $G_1$ . However, the difference between the sizes of the bipartitions of $G_1$ is $1$ , which is not divisible by $\mathrm {hcf}_{\xi }(H) = 2$ . Thus, by Claim1, the graph $G_1$ does not contain a perfect $H$ -subdivision tiling since $G_1$ is a bipartite graph, so every subdivision of $H$ in $G$ is also bipartite. Therefore, $G$ does not have a perfect $H$ -subdivision tiling.

Proof. It suffices to show that $\chi _{cr}(H^*) \leq \xi (H)$ . We recall that $X_H$ is a subset of $V(H)$ such that $f_H(X_H) = \xi (H)$ . Let $Y_H \,:\!=\, V(H)\setminus X_H$ . Let $A = X_H$ and $B = Y_H$ . Since $H^*$ is obtained by replacing all edges in $H[X_H]$ and $H[Y_H]$ with vertex-disjoint paths of length two, we update the set $B$ by adding vertices that were used to replace the edges in $H[X_H]$ . Similarly, we update the set $A$ by adding vertices that were used to replace the edges in $H[Y_H]$ . Then $A$ and $B$ are independent sets and $|B| = |Y_H| + e(H[X_H])$ . Thus, by the definition of $\sigma (H^*)$ , the inequality $\sigma (H^*) \leq |Y_H| + e(H[X_H])$ holds. This implies $\chi _{cr}(H^*) \leq \frac {v(H^*)}{v(H^*) - (|Y_H| + e(H[X_H]))} = \frac {v(H)+ e(H[X_H]) + e(H[Y_H])}{|X_H| + e(H[Y_H])} = \xi (H)$ .

Proof. Let $ c = \min \{\frac {\alpha }{2}, \frac {d}{10}\}$ . Consider a random family $ \mathcal {T}$ of size $ t$ subsets of $ Y$ , such that each set in $ \binom {Y}{t}$ is selected independently at random with the probability $ p = \frac {c}{n^{t - 1}}$ . Then $ |\mathcal {T}|$ has a binomial distribution with an expectation less than or equal to $ \frac {\alpha }{2 t} n$ . By Chebyshev’s inequality, with probability $ 1 - o(1)$ , the following holds.

(1) \begin{equation} |\mathcal {T}| \leq \frac {\alpha }{t} n. \end{equation}

For each $ x \in X$ , let $ \mathcal {Z}_x \,:\!=\, \{Z \subseteq Y\,:\, (x, Z) \in \mathcal {P}\}$ . Then the size $ |\mathcal {T} \cap \mathcal {Z}_x|$ has a binomial distribution with an expectation $ |\mathcal {Z}_x| p \geq cd n$ for every $ x \in X$ . By Chernoff bound, for each $ x \in X$ , the inequality $ |\mathcal {T} \cap \mathcal {Z}_x| \geq \frac {cd}{2} n$ holds with probability $ 1 - o(n^{-3})$ . Since $ |X| \leq n^2$ , we have the following with probability $ 1 - o(1)$ .

(2) \begin{equation} |\mathcal {T} \cap \mathcal {Z}_x| \geq \frac {cd}{2} n \text { for all } x \in Z. \end{equation}

We now count the number of intersecting pairs in $ \mathcal {T}$ . Let $ I$ be a random variable which is the number of intersecting pairs of $ \mathcal {T}$ . Since we have $ |\{(P, Q)\,:\, P, Q \subseteq [n],\text { } P \cap Q \neq \textit ptyset, \text { and } |P| = |Q| = t\}| \leq n^{2t - 1}$ , and each $ P$ , $ Q$ are chosen to be in $ \mathcal {T}$ with probability $ p = \frac {c}{n^{t-1}}$ , we have $ \mathbb {E}(I) \leq c^2 n$ . By Markov’s inequality, with probability at least $ \frac {1}{2}$ ,

(3) \begin{equation} |I| \leq 2c^2 n. \end{equation}

Thus, for all sufficiently large $ n$ , there is a family $ \mathcal {T}$ that satisfies all Equations (1) to (3). Let $ \mathcal {Y}$ be a collection obtained from $ \mathcal {T}$ by removing intersecting pairs from $ \mathcal {T}$ and removing at most one arbitrary element to ensure that $ |\mathcal {Y}|$ is even.

Then $ \mathcal {Y}$ is a collection of pairwise disjoint sets and by (1), we have $ |\mathcal {Y}| \leq |\mathcal {T}| \leq \frac {\alpha }{t} n$ and $ |\mathcal {Y}|$ is even. By (2) and (3), the size of the intersection $ |\mathcal {Y} \cap \mathcal {Z}_x| \geq \frac {cd}{2} n - 2c^2 n - 1 \geq \frac {\alpha d^2}{100} n$ for all $ x \in X$ . We now set $ \beta = \frac {\alpha d^2}{100}$ . Then $ \mathcal {Y}$ is the desired collection. This completes the proof.

Proof. Let $X = V(G) \setminus B.$ Let $\mathcal {P} = \{(x, \{y\}) \in X \times \binom {V(G)}{1} \,:\, xy \in E(G[X, B])\}.$ Then $\mathcal {P}$ is an $(n, 1, \eta )$ -family on $(X, V(G)).$ As $\frac {1}{n} \ll \beta \ll \alpha , \eta$ , by applying Lemma4.9 with the parameters $\alpha$ , $\eta$ , $\beta$ , and $n$ playing the roles of $\alpha$ , $d$ , $\beta$ , and $n$ , respectively, we obtain $\mathcal {Y} \subseteq \binom {B}{1}$ satisfying the following. $|\mathcal {Y}| \leq \alpha n$ and $|\{(v, \{b\}) \in \mathcal {P} \,:\, \{b\} \in \mathcal {Y}\}| \geq \beta n$ for all $x \in X.$ Let $B^{\prime} = \bigcup _{\{b\} \in \mathcal {Y}} \{b\}.$ Then $|B^{\prime}| \leq \alpha n$ and for any vertex $v \in V(G) \setminus B$ , the degree $d(v, B^{\prime}) \geq \beta n.$ Thus, for any subset $U \subseteq V(G) \setminus B$ with size at most $\beta n$ , we can find a matching $M$ greedily in $G[U, B^{\prime}]$ which covers all vertices of $U.$

Proof. We recall that $\hat {S}_H$ is a graph defined in Definition4.6 which has two vertices $u$ and $v$ such that both $S_H - u$ and $S_H - v$ contain spanning subdivisions of $H.$

Let

\begin{align*}\mathcal {P} = \{(u, Z) \in U \times \binom {V(G)}{v(S_H) + 1} \,:\, \exists v \in Z \cap B \text { s.t. } Z - v \text { is a } \mathrm {Sub}(H) \text {-exchanger for } \{u, v\}\}.\end{align*}

For each $u \in U$ , the number of pairs $(v, S) \in B \times \binom {V(G)}{v(S_H)}$ such that $S$ is a $\mathrm {Sub}(H)$ -exchanger for $\{u, v\}$ is at least $\frac {\eta d}{3} n^{v(S_H) + 1}.$ Thus, $\mathcal {P}$ is an $(n, v(S_H) + 1, \frac {\eta d}{3(v(S_H) + 1)})$ -family on $(U, V(G)).$

As $v(S_H) + 1 \leq h^2$ and $\frac {1}{n}, \beta \ll d, \alpha , \eta , \frac {1}{h}$ , by applying Lemma4.9 with $v(S_H) + 1$ , $\alpha$ , $\frac {\eta d}{3(v(S_H) + 1)}$ and $\beta (v(S_H) + 1)$ playing the roles of $t$ , $\alpha$ , $d$ , and $\beta$ , respectively, we obtain a collection of vertex-disjoint subsets $\mathcal {Y} \subseteq \binom {V(G)}{v(S_H) + 1}$ satisfying the following.

1. 1. $|\mathcal {Y}| \leq \frac {\alpha }{v(S_H) + 1} n$ ,

2. 2. $|\{Z \in \mathcal {Y} \,:\, (u, Z) \in \mathcal {P} \}| \geq \beta (v(S_H) + 1) n$ for all $u \in U.$

Let $A \,:\!=\, \bigcup _{Z \in \mathcal {Y}} Z.$ Then $|A| \leq \alpha n.$ Let $U^{\prime} \subseteq U \setminus A$ with size at most $\beta n.$ By our choice of $U$ and $\mathcal {Y}$ , for each vertex $x \in U^{\prime}$ , there are at least $\frac {\beta (v(S_H) + 1)}{v(S_H) + 1} n = \beta n$ distinct pairs $(u, v)$ which use distinct $\mathrm {Sub}(H)$ -exchangers in $\mathcal {Y}$ such that $v \in A \cap B$ and there is $Z \in \mathcal {Y}$ , where $v \in Z$ and $Z - v$ is a $\mathrm {Sub}(H)$ -exchanger for $\{u, v\}.$ Thus, we can greedily exchange all vertices in $U^{\prime}$ with a set of distinct vertices $W$ , by using $\mathrm {Sub}(H)$ -exchangers, where $W \subseteq A \cap B$ and $|W| = |U^{\prime}|.$