Thomas Schweser, Michael Stiebitz

^aTechnische Universitat Ilmenau, Inst. of Math., PF 100565, D-98684 Ilmenau, Germany. ¨

thomas.schweser@tu-ilmenau.de, michael.stiebitz@tu-ilmenau.de

In 2007 Matamala proved that if G is a simple graph with maximum degree ∆ ≥ 3 not containing K∆+1 as a subgraph and s, t are positive integers such that s + t ≥ ∆, then the vertex set of G admits a partition (S, T) such that G[S] is a maximum order (s − 1)-degenerate subgraph of G and G[T] is a (t − 1)-degenerate subgraph of G. This result extended earlier results obtained by Borodin, by Bollobas and Manvel, by Catlin, by Gerencs ´ er and by Catlin and Lai. In this paper we ´ prove a hypergraph version of this result and extend it to variable degeneracy and to partitions into more than two parts, thereby extending a result by Borodin, Kostochka, and Toft.

Keywords: hypergraph decomposition; vertex partition; degeneracy; coloring of hypergraphs

Mathematics Subject Classification : 05C15

DOI: 10.5614/ejgta.2021.9.1.1

1. Introduction and main results

The paper deals with partition of hypergraphs into a fixed number of subhypergraphs so that each part satisfies a certain degree condition. Graphs and hypergraphs considered in this paper may have parallel edges, but no loops. We will mainly use the notation from the paper [19]. Let G be a hypergraph. As usual, we denote by V (G) the vertex set of G and by E(G) the edge set of G. For a vertex v of G, let EG(v) denote the set of edges of G that are incident with v in G. Then dG(v) = |EG(v)| is the degree of v in G, and ∆(G) = maxv∈^V (G) dG(v) is the maximum degree of G. Given two vertices v 6= w of a hypergraph G, a (v, w)-hyperpath of length

Received: 21 July 2018, Revised: 9 December 2020, Accepted: 15 December 2020.

q in G is a sequence (v1, e1, v2, e2, . . . , vq, eq, vq+1) of distinct vertices v1, v2, . . . , vq+1 of G and distinct edges e1, e2, . . . , e^q of G such that v¹ = v, vq+1 = w, and eⁱ ∈ EG(vi) ∩ EG(vi+1) for i ∈ {1, 2, . . . , q}. By distG(v, w) we denote the length of a shortest (v, w)-hyperpath in G. The hypergraph G is connected if for any two vertices v, w of G there is a (v, w)-hyperpath in G. A (connected) component of a nonempty hypergraph G is a maximal connected subhypergraph.

For a vertex set X ⊆ V (G), we denote by G[X] the subhypergraph of G induced by X, that is, the hypergraph whose vertex set is X and whose edges are all edges of G that are incident only to vertices in X. Furthermore, G − X = G[V (G) \ X]. If X = {v} is a singleton, then we also write G − v instead of G − X. A subgraph H of G is an induced subhypergraph of G if V (H) ⊆ V (G) and H = G[V (H)]. If H is an induced subhypergraph of G and v ∈ V (G), then H + v = G[V (H) ∪ {v}]. A partition of a hypergraph G is a sequence of induced subhypergraphs of G (possibly empty) such that each vertex belongs to exactly one hypergraph of the sequence.

The first result dealing with partition of graphs under degree constraints was obtained in 1966 by Lovasz [16]. He proved that if ´ G is a simple graph and d1, d2, . . . , d^p are non-negative integers such that d¹ + d² + · · · + d^p ≥ ∆(G) − p + 1, then there is a partition (G1, G2, . . . , Gp) of G such that ∆(Gi) ≤ dⁱ for 1 ≤ i ≤ p. It is easy to see that Lovasz's partition result also holds for ´ hypergraphs; one can apply the same simple argument as in Lovasz's original proof. Csisz ´ ar and ´ Korner [8] used Lov ¨ asz's argument to derive a continues version of his partition result for edge ´ weighted graphs; they used this result for proving coding theorems. A variable version of Lovasz's ´ result was obtained in 1977 by Borodin and Kostochka [3]. They proved that if G is a simple graph and f1, f2, . . . , f^p : V (G) → N⁰ are p vertex functions such that f1(v) + f2(v) + · · · + fp(v) ≥ dG(v) − p + 1 for all v ∈ V (G), then G has a partition (G1, G2, . . . , Gp) such that d^Gi (v) ≤ fi(v) whenever v ∈ V (Gi) and i ∈ {1, 2, . . . , p}. Also this result can easily be extended to hypergraphs.

The coloring number col(G) of a non-empty hypergraph G is 1 plus the maximum minimum degree of the subhypergraphs of G. If G is the empty hypergraph (that is, V (G) = E(G) = ∅), we set col(G) = 0. So if d is a non-negative integer, then col(G) ≤ d if and only if every non-empty subhypergraph of G contains a vertex of degree at most d−1. In particular, col(G) ≤ 0 if and only if G is empty and col(G) ≤ 1 if and only if G is edgeless.

Borodin [2] and, independently, Bollobas and Manvel [1] proved that if ´ G is a connected simple graph with maximum degree ∆ ≥ 3 different from K∆+1 and d1, d2, . . . , d^p are positive integers such that d¹ + d² + · · · + d^p ≥ ∆, then G has a partition (G1, G2, . . . , Gp) such that col(Gi) ≤ dⁱ for 1 ≤ i ≤ p. The famous theorem of Brooks [5], saying that a connected simple graph with maximum degree ∆ ≥ 3 satisfies χ(G) ≤ ∆ + 1 and equality holds if and only if G = K∆+1, follows from the former result by taking p = ∆ and dⁱ = 1 for 1 ≤ i ≤ p. Here χ(G) denotes the chromatic number of G, that is, the least integer p such that G has a partition into p edgeless subgraphs. The cases of point aboricity (which correspond to d¹ = d² = · · · = d^p = 2), and of point partiton numbers in general (which corresponds to d¹ = d² = · · · = dp) were solved by Kronk and Mitchem [13], and Mitchem [18]. The point partition number was introduced by Lick and White [15].

A variable version of the result by Borodin, respectively Bollobas and Manvel, was obtained in ´ 2000 by Borodin, Kostochka, and Toft [4] for simple graphs. Schweser and Stiebitz [19] extended this result to hypergraphs. Let G be a hypergraph, and let h : V (G) → N⁰ be a function from the vertex set of G into the set of non-negative integers. The hypergraph G is said to be strictly

h-degenerate if every non-empty subhypergraph H of G has a vertex v such that dH(v) ≤ h(v) − 1. Note that if h(v) ≡ d is the constant function, then G is strictly h-degenerate if and only if col(G) ≤ d. Degeneracy of graphs was introduced by Lick and White [14]. The hypergraph G is called h-regular if dG(v) = h(v) for all v ∈ V (G).

Let G be an arbitrary hypergraph. A function f : V (G) → N p 0 is called a vector function of G. By fⁱ we name the ith coordinate of f, i.e., f = (f1, f2, . . . , fp). The set of all vector functions of G with p coordinates is denoted by Vp(G). For f ∈ Vp(G), an f-partition of G is a partition (G1, G2, . . . , Gp) of G such that Gⁱ is strictly fi-degenerate for all i ∈ {1, 2, . . . , p}. If the hypergraph G admits an f-partition, then G is said to be f-partitionable.

Recall that a block of a hypergraph G is a maximal connected subhypergraph of G without a separating vertex. If G itself has no separating vertex, G is said to be a block. For a simple graph H and an integer t ≥ 1, let G = tH denote the graph obtained from H by replacing each edge of H by t parallel edges.

Let G be a connected hypergraph and let f ∈ Vp(G) be a vector-function for some integer p ≥ 1. We say that (G, f) is a hard pair if one of the following four conditions holds.

(1) G is a block and there exists an index j ∈ {1, 2, . . . , p} such that

\[f_i(v) = \begin{cases} d_H(v) & \text{if } i = j, \\ 0 & \text{otherwise} \end{cases}\]

for all i ∈ {1, 2, . . . , p} and for each v ∈ V (G).

(2) G = tKⁿ for some t ≥ 1, n ≥ 3 and there are integers n1, n2, . . . , n^p ≥ 0 with at least two nⁱ different from zero such that n¹ + n² + . . . + n^p = n − 1 and that

\[f(v) = (tn_1, tn_2, \dots, tn_p)\]

for all v ∈ V (G).

(3) G = tCⁿ with t ≥ 1 and n ≥ 5 odd and there are two indices k 6= ` from the set {1, 2, . . . , p} such that

\[f_i(v) = \begin{cases} t & \text{if } i \in \{k, \ell\}, \\ 0 & \text{otherwise} \end{cases}\]

for all i ∈ {1, 2, . . . , p} and for each v ∈ V (G). In this case, we say that G is a block of type (C).

(4) There are two disjoint hard pairs (G¹ , f ¹ ) and (G² , f ² ) with f ¹ ∈ Vp(G¹ ) and f ² ∈ Vp(G² ) such that G is obtained from G¹ and G² by merging two vertices v ¹ ∈ V (G1) and v ² ∈ V (G2) to a new vertex v ∗ (see Figure 1). Furthermore, it holds

\[f(v) = \begin{cases} f^{1}(v) & \text{if } v \in V(H_{1}) \setminus \{v^{1}\}, \\ f^{2}(v) & \text{if } v \in V(H_{2}) \setminus \{v^{2}\}, \\ f^{1}(v^{1}) + f^{2}(v^{2}) & \text{if } v = v^{*} \end{cases}\]

for all v ∈ V (G). In this case we say that (G, f) is obtained from (G¹ , f ¹ ) and (G² , f ² ) by merging v 1 and v 2 to v ∗ .

Figure 1. Merging two hard pairs.

Note that a hypergraph G is f-partitionable if and only if each component of G is f-partitionable. Thus, it is sufficient to consider only connected hypergraphs. The next result was proved by Schweser and Stiebitz [19]; for the class of simple graphs it was proved in 2000 by Borodin, Kostochka and Toft [4].

Theorem 1.1. Let G be a connected hypergraph and let f ∈ Vp(G) be a vector function with p ≥ 1 such that f1(v) + f2(v) + · · · + fp(v) ≥ dG(v) for all v ∈ V (G). Then, G is f-partitionable if and only if (G, f) is not a hard pair.

On the one hand, Theorem 1.1 is a strengthening of the result by Borodin, respectively Bollobas´ and Manvel. On the other hand, as explained in [19], Theorem 1.1 implies several well known result about colorings and list-colorings of graphs, respectively hypergraphs; in particular, the characterization of degree choosable graphs obtained by Erdos, Rubin, and Taylor [9] and the ˝ characterization of degree choosable hypergraphs given by Kostochka, Stiebitz, and Wirth [12]. The special case when p = ∆(G) and fi(v) = 1 for all v ∈ V (G) and 1 ≤ i ≤ p yields a Brooks-type result for hypergraphs which was obtained by Jones [11].

In 2007 Matamala [17] obtained another strengthening of the result by Borodin, respectively Bollobas and Manvel. He proved that if ´ G is a simple graph with maximum degree ∆ ≥ 3 not

containing a K∆+1 as a subgraph and d1, d² are positive integers with d¹ + d² ≥ ∆, then there is a partition (G1, G2) of G such that G¹ is a maximum order induced subgraph with col(G1) ≤ d¹ and col(G2) ≤ d2. This result improves earlier results obtained by Catlin [6], Gerencser [10], ´ and Catlin and Lai [7]. Catlin and Gerencser proved that if ´ G is a simple graph with maximum degree ∆ ≥ 3 not containing a K∆+1, then G has a ∆-coloring in which one color class is a maximum independent set. The main result of this paper is the following generalization of Matamala's theorem.

Theorem 1.2. Let G be a hypergraph and let f ∈ Vp(G) be a vector function of G with p ≥ 2 such that f1(v) + f2(v) + · · · + fp(v) ≥ dG(v) for all v ∈ V (G). Furthermore, assume that if G⁰ is a component of G, then (G⁰ , f) is not a hard pair. Then, there is a partition (G1, G2, . . . , Gp) of G such that G¹ is a maximum order strictly f1-degenerate subhypergraph of G, and for i ∈ {2, 3, . . . , p − 1}, the hypergraph Gⁱ is a maximum order strictly fi-degenerate subhypergraph of G − (V (G1) ∪ V (G2) ∪ · · · ∪ V (Gi−1)).

2. Proof of Theorem 1.2

Proposition 2.1. Let G be a hypergraph, and let f ∈ Vp(G) be a vector function of G with p ≥ 1, and let h : V (G) → N⁰ be the function with h(v) = f1(v) + f2(v) + · · · + fp(v) for all v ∈ V (G). If G is strictly h-degenerate, then G is f-partitionable.

Proof. The proof is by induction on the order n = |G| of G. If n = 1, then V (G) = {v} consists of only one vertex and, as G is strictly h-degenerate, 0 = dG(v) < h(v) = f1(v)+f2(v)+. . .+fp(v), which implies that there is an index i ∈ {1, 2, . . . , p} such that fi(v) > 0. Setting Gⁱ = G[{v}] and G^j = ∅ for j 6= i from {1, 2, . . . , p} then gives us the f-partition (G1, G2, . . . , Gp) as claimed. Now assume n ≥ 2. Since G is strictly h-degenerate, there is a vertex v ∈ V (G) with dG(v) < h(v). Clearly, G − v is strictly h-degenerate, and so G − v admits an f-partition (G1, G2, . . . , Gp) (by induction hypothesis). As dG(v) < h(v) = f1(v) + f2(v) + . . . + fp(v), it follows from the pigeonhole principle that d^Gi (v) < fi(v) for some i ∈ {1, 2, . . . , p}, say for i = 1. Then, G¹ + v is strictly f1-degenerate and so (G¹ + v, G2, . . . , Gp) is an f-partition of G, as claimed. This completes the proof.

Proposition 2.2. Let G be a connected hypergraph, and let f ∈ Vp(G) be a vector function of G with p ≥ 1 such that f1(v) + f2(v) + . . . + fp(v) ≥ dG(v) for all v ∈ V (G). If G is not f-partitionable, then f1(v) + f2(v) + . . . + fp(v) = dG(v) for all v ∈ V (G).

Proof. Let h : V (G) → N⁰ with h(v) = f1(v) + f2(v) + . . . + fp(v) for all v ∈ V (G). Then, dG(v) ≤ h(v) for all v ∈ V (G). Assume that there is a vertex u ∈ V (G) with dG(u) < f1(v) + f2(v) + . . . + fp(v) = h(u). As G is connected, it then follows that G is strictly h-degenerate. Proposition 2.1 then implies that G admits an f-partition, a contradiction.

Lemma 2.1. Let G be a hypergraph and let f ∈ Vp(G) be a vector function of G with p ≥ 2 such that f1(v) + f2(v) + · · · + fp(v) ≥ dG(v) for all v ∈ V (G). If G is f-partitionable, then there is an f-partition (G1, G2, . . . , Gp) of G such that G¹ is a maximum order strictly f1-degenerate subhypergraph of G.

Proof. The lemma's proof is by reductio ad absurdum. To this end, let \(\mathcal{F}\) denote the set of tuples \((G_1,G_2,\ldots,G_p,G_1^*,G_2^*)\) such that \((G_1,G_2,\ldots,G_p)\) is an f-partition of G, \(G_1^*\) is a maximum order strictly \(f_1\)-degenerate subhypergraph of G, and \(G_2^*=G\setminus V(G_1^*)\). Furthermore, let \(f'=(f_2,f_3,\ldots,f_p)\) and let \(h=f_2+f_3+\cdots+f_p\). By assumption, G has an f-partition. Clearly, G has a maximum order strictly \(f_1\)-degenerate subhypergraph. Hence, \(\mathcal{F}\) is non-empty.

Claim 1. Let \((G_1, G_2, \dots, G_p, G_1^*, G_2^*) \in \mathcal{F}\) be an arbitrary tuple. Then, the following statements hold:

• (a) Let \(v \in V(G_2^*)\) be an arbitrary vertex. Then, there is a hypergraph \(H \subseteq G_1^* + v\) with \(d_H(w) \ge f_1(w)\) for all \(w \in V(H)\) and each such hypergraph contains the vertex v. As as a consequence, \(d_{G_2^*}(v) \le f_2(v) + f_3(v) + \ldots + f_p(v) = h(v)\) for all \(v \in V(G_2^*)\).
• (b) The hypergraph \(G_2^*\) is not f'-partitionable and any non-f'-partitionable component K of \(G_2^*\) is h-regular and contains a vertex \(v^*\) from \(G_1\).
• (c) Let K be a non-f'-partitionable component of \(G_2^*\) and let \(v^* \in V(K) \cap V(G_1)\). Moreover, let \(H \subseteq G_1^* + v^*\) be a hypergraph with \(d_H(w) \ge f_1(w)\) for all \(w \in V(H)\). Then, H contains a vertex \(w^*\) from \(V(G) \setminus V(G_1)\).
• (d) Let K be a non-f'-partitionable component of \(G_2^*\) and let \(v^* \in V(K) \cap V(G_1)\). Moreover, let \(H \subseteq G_1^* + v^*\) be a hypergraph with \(d_H(w) \ge f_1(w)\) for all \(w \in V(H)\) and let \(u^*\) be a vertex that is adjacent to \(v^*\) in H. Then, \(\tilde{G}_1 = G_1^* + v^* u^*\) is a maximum order strictly \(f_1\)-degenerate subhypergraph of G and with \(\tilde{G}_2 = G_2^* + u^* v^*\) we have \((G_1, G_2, \ldots, G_p, \tilde{G}_1, \tilde{G}_2) \in \mathcal{F}\). Furthermore, \(\tilde{G}_2\) has at most as many non-f'-partitionable components as \(G_2^*\) and if equality holds, then \(u^*\) is contained in a non-f'-partitionable component of \(\tilde{G}_2\).

Proof: For the proof of (a) let \(v \in V(G_2^*)\) be an arbitrary vertex. Since \(G_1^*\) is a maximum order strictly \(f_1\)-degenerate subhypergraph, \(G_1^* + v\) is not strictly \(f_1\)-degenerate and, thus, there is a subhypergraph H of \(G_1^* + v\) such that \(d_H(w) \ge f_1(w)\) for all \(w \in V(H)\). As \(G_1\) is strictly \(f_1\)-degenerate, H contains the vertex v and so \(d_{G_1^*}(v) \ge d_H(v) \ge f_1(v)\). As \(d_{G_1^*}(v) + d_{G_2^*}(v) \le d_G(v) \le f_1(v) + f_2(v) + \ldots + f_p(v)\), this implies that \(d_{G_2^*}(v) \le f_2(v) + f_3(v) + \ldots + f_p(v)\), which proves statement (a).

For the proof of (b) assume that \(G_2^*\) admits an f'-partition \((G_2', G_3', \dots G_p')\). Then, the tuple \((G_1^*, G_2', G_3', \dots, G_p')\) is an f-partition of G such that \(G_1^*\) is a maximum order strictly \(f_1\)-degenerate subhypergraph of G, contradicting the assumption that the lemma is wrong. Hence, \(G_2^*\) is not f'-partitionable, i.e., \(G_2^*\) has at least one non-f'-partitionable component. Now let K be a non-f'-partitionable component of \(G_2^*\). Then, by (a) and by Proposition 2.2, \(d_K(v) = d_{G_2^*}(v) = f_2(v) + f_3(v) + \ldots + f_p(v)\) for all \(v \in V(K)\), i.e. K is h-regular. As \(G - V(G_1)\) is f'-partitionable, K clearly contains a vertex \(v^*\) from \(G_1\). This proves (b).

For the proof of (c) and (d), let \(H \subseteq G_1^* + v^*\) be a hypergraph with \(d_H(w) \ge f_1(w)\) for all \(w \in V(H)\) (which exists by (a)). By (a), H contains the vertex \(v^*\). As \(G_1\) is strictly \(f_1\)-degenerate, H contains a vertex \(w^*\) from \(V(G) \setminus V(G_1)\), which proves (c). Now let \(u^*\) be a vertex that is adjacent to \(v^*\) in H. Then, \(d_{G_2^*}(v^*) = d_K(v^*) = f_2(v^*) + f_3(v^*) + \ldots + f_p(v^*)\) (by (b)), \(d_{G_1^*}(v^*) \ge d_H(v^*) \ge d_H(v^*)\)

\(f_1(v^*)\), and \(d_{G_1^*}(v^*) + d_{G_2^*}(v^*) \leq d_G(v^*) \leq f_1(v^*) + f_2(v^*) + \ldots + f_p(v^*)\). As a consequence, we have \(d_{G_1^*}(v^*) = f_1(v^*)\) and so \(d_{G_1^*}(v^*) = d_H(v^*)\). Hence, \(d_{G_1^*-u^*}(v^*) < f_1(v^*)\). As \(G_1^* - u^* \subseteq G_1^*\) and \(G_1^*\) is strictly \(f_1\)-degenerate, this implies that \(G_1^* + v^* - u^*\) is strictly \(f_1\)-degenerate as well and so \(\tilde{G}_1 = G_1^* + v^* - u^*\) is a maximum order strictly \(f_1\)-degenerate subhypergraph of G. Note that \(K - v^*\) is f'-partitionable (as K is h-regular by (b) and by Proposition 2.2) and so \(G_2^* - v^*\) has one non-f'-partitionable component less than \(G_2^*\). Clearly, \(\tilde{G}_2 = G_2^* - v^* + u^*\) may have only one more non-f'-partitionable component than \(G_2^* - v^*\) and if so, \(u^*\) must be contained in this component. Since \(\tilde{G}_1\) is a maximum order strictly \(f_1\)-degenerate subhypergraph of G, \((G_1, G_2, \ldots, G_p, \tilde{G}_1, \tilde{G}_2) \in \mathcal{F}\) and the proof is complete.

Let \((G_1,G_2,\ldots,G_p,G_1^*,G_2^*)\in\mathcal{F}\) be an arbitrary tuple. Since we assume that the lemma is false, \(|G_1|<|G_1^*|\). By Claim 1(b), \(G_2^*\) is not f'-partitionable and so there is a non-f'-partitionable component of \(G_2^*\). Let \(\mathcal{K}_{(G_1,G_2,\ldots,G_p,G_1^*,G_2^*)}\) denote the set of non f'-partitionable components of \(G_2^*\). Then, by Claim 1(c), for any \(K\in\mathcal{K}_{(G_1,G_2,\ldots,G_p,G_1^*,G_2^*)}\) we have \(V(K)\cap V(G_1)\neq\varnothing\). Let

\[V_{(G_1,G_2,\dots,G_p,G_1^*,G_2^*)} = \bigcup_{K \in \mathcal{K}_{(G_1,G_2,\dots,G_p,G_1^*,G_2^*)}} (V(K) \cap V(G_1))\]

and let \(\mathcal{T}_{(G_1,G_2,...,G_p,G_1^*,G_2^*)}\) denote the set of tupels \((v^*,H,w^*)\) such that \(v^* \in V_{(G_1,G_2,...,G_p,G_1^*,G_2^*)}\), H is a subhypergraph of \(G_1^* + v^*\) with \(d_H(w) \geq f_1(w)\) for all \(w \in V(H)\) and \(w^* \in V(H) \setminus V(G_1)\). By Claim 1(a),(c), each vertex \(v^* \in V_{(G_1,G_2,...,G_p,G_1^*,G_2^*)}\) is contained in some tuple from \(\mathcal{T}_{(G_1,G_2,...,G_p,G_1^*,G_2^*)}\).

Now we choose \((G_1, G_2, \dots, G_p, G_1^*, G_2^*) \in \mathcal{F}\) such that

• (1) \(|G_1 \cap G_1^*|\) is maximum.
• (2) \(|\mathcal{K}_{(G_1,G_2,...,G_n,G_1^*,G_2^*)}|\) is minimum subject to (1).
• (3) \(m = \min\{\operatorname{dist}_H(v^*, w^*) \mid (v^*, H, w^*) \in \mathcal{T}_{(G_1, G_2, \dots, G_p, G_1^*, G_2^*)}\}\) is minimum subject to (1),(2).

Let \((v^*, H, w^*) \in \mathcal{T}_{(G_1, G_2, \dots, G_p, G_1^*, G_2^*)}\) such that \(d_H(v^*, w^*) = m\). If m = 1, then \(w^*\) is in H adjacent to \(v^*\) and it follows from Claim 1(d) that \(\tilde{G}_1 = G_1^* + v^* - w^*\) is a maximum order strictly \(f_1\)-degenerate subgraph of G. Moreover, \(|V(G_1) \cap V(\tilde{G}_1)| > |V(G_1) \cap V(G_1^*)|\), contradicting (1). Hence, \(m \geq 2\). Let \(u^*\) be a vertex that is adjacent to \(v^*\) in H and is contained in a shortest \((v^*, w^*)\)-hyperpath of H. As \(m \geq 2\) and by (3), \(u^* \in V(G_1)\). By Claim 1(d), \(\tilde{G}_1 = G_1 + v^* - u^*\) is a maximum order strictly \(f_1\)-degenerate subhypergraph of G and \(\tilde{G}_2 = G_2 + u^* - v^*\) has at most \(|\mathcal{K}_{(G_1,G_2,\dots,G_p,G_1^*,G_2^*)}|\) non-f'-partitionable components. By (2), \(\tilde{G}_2\) has exactly \(|\mathcal{K}_{(G_1,G_2,\dots,G_p,G_1^*,G_2^*)}|\) non-f'-partitionable components implying (by Claim 1(d)) that \(u^*\) is contained in a non-f'-partitionable component K of \(\tilde{G}_2\). Then, \((G_1,G_2,\dots,G_p,\tilde{G}_1,\tilde{G}_2) \in \mathcal{F}\) is a tuple satisfying (1) and (2) and \((u^*,H,w^*) \in \mathcal{T}_{(G_1,G_2,\dots,G_p,\tilde{G}_1,\tilde{G}_2)}\) with \(d_H(u^*,w^*) < d_H(v^*,w^*) = m\), contradicting (3). This proves the lemma.

Lemma 2.2. Let G be a hypergraph and let \(f \in \mathcal{V}_p(G)\) be a vector function of G with \(p \geq 2\) such that \(f_1(v) + f_2(v) + \cdots + f_p(v) \geq d_G(v)\) for all \(v \in V(G)\). If G is f-partitionable, then there is a partition \((G_1, G_2, \ldots, G_p)\) of G such that \(G_1\) is a maximum order strictly \(f_1\)-degenerate subhypergraph of G, and for \(i \in \{2, 3, \ldots, p-1\}\), the hypergraph \(G_i\) is a maximum order strictly \(f_i\)-degenerate subhypergraph of \(G - (V(G_1) \cup V(G_2) \cup \cdots \cup V(G_{i-1}))\).

Proof. It follows from Lemma 2.1 that G has an f-partition (G1, G2, . . . , Gp) such that G¹ is a maximum order strictly f1-degenerate subhypergraph. Let G⁰ = G − V (G1). We claim that f2(v) + f3(v) + . . . + fp(v) ≥ dG⁰(v) for all v ∈ V (G⁰ ). Otherwise, f2(v) + f3(v) + . . . + fp(v) < dG⁰(v) for some v ∈ V (G⁰ ) and, as f1(v) + f2(v) + . . . + fp(v) ≥ dG(v), we conclude d^G1 (v) < f1(v). As a consequence, G¹ + v is a strictly f1-degenerate subhypergraph of G with |G¹ + v| > |G1|, contradicting the maximality of G1. Hence, f2(v) + f3(v) + . . . + fp(v) ≥ dG⁰(v) for all v ∈ V (G⁰ ). Let f ⁰ = (f2, f3, . . . , fp). Since (G2, G3, . . . , Gp) is an f 0 -partition of G⁰ , we can again apply Lemma 2.1 and obtain an f 0 -partition (G⁰ 2 , G⁰ 3 , . . . , G⁰ p ) of G⁰ such that G⁰ 2 is a maximum order strictly f2-degenerate subhypergraph. By repeated application of the above arguments we finally obtain an f-partition as required.

Clearly, Theorem 1.2 is a direct consequence of Theorem 1.1 and the above lemma and so the proof is complete. The next corollary can be deduced easily from Theorem 1.1 and Theorem 1.2.

Corollary 2.1. Let G be a connected hypergraph having maximum degree ∆ ≥ 1. Moreover, let d1, d2, . . . , d^p be positive integers, p ≥ 2, such that d¹ + d² + . . . + d^p ≥ ∆. Then, there is a partition (G1, G2, . . . , Gp) of G such that G¹ is a maximum order subhypergraph of G with col(G1) ≤ d1, and for i ∈ {2, 3, . . . , p−1}, the hypergraph Gⁱ is a maximum order subhypergraph of G−((V (G1))∪V (G2)∪· · ·∪V (Gi−1)) with col(Gi) ≤ dⁱ , unless G is a tKⁿ for some t, n ≥ 1, dⁱ = tnⁱ for some nⁱ ≥ 1, i ∈ {1, 2, . . . , p}, and d¹ + d² + . . . + d^p = t(n − 1) = ∆, or G = tCⁿ for t ≥ 1 and n ≥ 3 odd, p = 2, and dⁱ = t for i ∈ {1, 2}.

Acknowledgement

The authors thank the Danish Research Council for support through the program Algodisc.

References

• [1] B. Bollobas, and B. Manvel, Optimal vertex partition, ´ Bull. Lond. Math. Soc. 11 (1979) 113– 116.
• [2] O. V. Borodin, On decomposition of graphs into degenerate subgraphs, Metody Diskret. Analiz. 28 (1976), 3–11 (in Russian).
• [3] O.V. Borodin and A.V. Kostochka, On an upper bound of a graph's chromatic number, depending on the graph's degree and density, J. Combin. Theory Ser. B 23 (1977), 247–250.
• [4] O. V. Borodin, A V. Kostochka and B. Toft, Variable degeneracy: extensions of Brooks' and Gallai's theorems, Discrete Math. 214 (2000), 101–112.
• [5] R. L. Brooks, On colouring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37 (1941), 194–197.
• [6] P. A. Catlin, Brooks' graph coloring theorem and the independence number, J. Combin. Theory Ser. B 27 (1979), 42–48.

• [7] P. A. Catlin and H. Lai, Vertex arboricity and maximum degree, Discrete Math. 141 (1995), 37–46.
• [8] I. Csiszar and J. Korner, Graph decomposition: a new key to coding theorems, in ´ IEEE Transactions on Information Theory 27 (1981), 5–12.
• [9] P. Erdos, A. L. Rubin, and H. Taylor, Choosability in graphs, ˝ Congr. Numer. XXVI (1979), 125–157.
• [10] L. Gerencser, Szinez ´ esi probl ´ em´ akrol, ´ Mat. Lapok. 16 (1965), 274–277.
• [11] R. P. Jones, Brooks' Theorem for hypergraphs, Congr. Numer. XV (1975), 379–384.
• [12] A. V. Kostochka, M. Stiebitz and B. Wirth, The colour theorems of Brooks and Gallai extended, Discrete Math. 162 (1996), 299–303.
• [13] H. V. Kronk and J. Mitchem, Critical point-arboritic graphs, J. Lond. Math. Soc. 9 (1975), 459–466.
• [14] D. R. Lick and A. T. White, k-degenerate graphs, Canad. J. Math. 22 (1970), 1082–1096.
• [15] D. R. Lick and A. T. White, The point partition numbers of closed 2-manifolds, J. Lond. Math. Soc. 4 (1972), 577–583.
• [16] L. Lovasz, On decomposition of graphs, ´ Studia Sci. Math. Hungar 1 (1966), 237–238.
• [17] M. Matamala, Vertex partition and maximum degenerate subgraphs, J. Graph Theory 55 (2007), 227–232.
• [18] J. Mitchem, An extension of Brooks' theorem to n-degenerate graphs, Discrete Math. 17 (1977), 291–298.
• [19] T. Schweser and M. Stiebitz, Partitions of hypergraphs under variable degeneracy constraints, J. Graph Theory 96 (2021), 7–33.