Vertex partition of hypergraphs and maximum degenerate subhypergraphs
Abstract
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 Gerencser 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
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.1.1
References
B. Bollob´as, and B. Manvel, Optimal vertex partition, Bull. Lond. Math. Soc. 11 (1979) 113–116.
O.V. Borodin, On decomposition of graphs into degenerate subgraphs, Metody Diskret. Analiz. 28 (1976), 3–11 (in Russian).
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.
O.V. Borodin, A.V. Kostochka and B. Toft, Variable degeneracy: extensions of Brooks’ and Gallai’s theorems, Discrete Math. 214 (2000), 101–112.
R.L. Brooks, On colouring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37 (1941), 194–197.
P.A. Catlin, Brooks graph coloring theorem and the independence number, J. Combin. Theory Ser. B 27 (1979), 42–48.
P.A. Catlin and H. Lai, Vertex arboricity and maximum degree, Discrete Math. 141 (1995), 37–46.
I. Csisz´ar and J. Korner, Graph decomposition: a new key to coding theorems, in IEEE Transactions on Information Theory 27 (1981), 5–12.
P. Erdos, A.L. Rubin, and H. Taylor, Choosability in graphs, Congr. Numer. XXVI (1979),
–157.
L. Gerencser, Szinezesi problemakrol, Mat. Lapok. 16 (1965), 274–277.
R.P. Jones, Brooks’ Theorem for hypergraphs, Congr. Numer. XV (1975), 379–384.
A.V. Kostochka, M. Stiebitz and B. Wirth, The colour theorems of Brooks and Gallai extended, Discrete Math. 162 (1996), 299–303.
H.V. Kronk and J. Mitchem, Critical point-arboritic graphs, J. Lond. Math. Soc. 9 (1975), 459–466.
D.R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970), 1082–1096.
D.R. Lick and A.T.White, The point partition numbers of closed 2-manifolds, J. Lond. Math. Soc. 4 (1972), 577–583.
L. Lovasz, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966), 237–238.
M. Matamala, Vertex partition and maximum degenerate subgraphs, J. Graph Theory 55 (2007), 227–232.
J. Mitchem, An extension of Brooks’ theorem to n-degenerate graphs, Discrete Math. 17 (1977), 291–298.
T. Schweser and M. Stiebitz, Partitions of hypergraphs under variable degeneracy constraints, J. Graph Theory 96 (2021), 7–33.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.