Vertex partition of hypergraphs and maximum degenerate subhypergraphs

DOI10.5614/EJGTA.2021.9.1.1MaRDI QIDQ4958039zbMATH OpenOpenAlexFDO

Authors Thomas Schweser, Michael Stiebitz

Publication date 6 September 2021

Published in Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

Full work available at URL https://arxiv.org/abs/1807.02308

zbMATH Keywords

degeneracyvertex partitionhypergraph decompositioncoloring of hypergraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: In 2007 Matamala proved that if $G$ is a simple graph with maximum degree $Deltageq3$ not containing $K_{Delta+1}$ as a subgraph and $s,t$ are positive integers such that $s+tgeqDelta$, 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 Bollob'as and Manvel, by Catlin, by Gerencs'{e}r 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.

Recommendations

• Vertex partitions and maximum degenerate subgraphs
• Partitioning a graph into degenerate subgraphs
• Graph decompositions without isolated vertices. II
• Destroying noncomplete regular components in graph partitions
• Partitioning into graphs with only small components

Cites work

• scientific article; zbMATH DE number 3661375 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3537704 (Why is no real title available?)
• scientific article; zbMATH DE number 3228454 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• k-Degenerate Graphs
• An extension of Brooks' theorem to n-degenerate graphs
• Brooks' graph-coloring theorem and the independence number
• Critical Point-Arboritic Graphs
• Graph decomposition: A new key to coding theorems
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Optimal Vertex Partitions
• Partitions of hypergraphs under variable degeneracy constraints
• The Point Partition Numbers of Closed 2-Manifolds
• The colour theorems of Brooks and Gallai extended
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• Vertex arboricity and maximum degree
• Vertex partitions and maximum degenerate subgraphs

Cited in

(4)

• Vertex partitions and maximum degenerate subgraphs
• Partitioning a graph into degenerate subgraphs
• Partitions of hypergraphs under variable degeneracy constraints
• Partitioning into degenerate graphs in linear time

This page was built for publication: Vertex partition of hypergraphs and maximum degenerate subhypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958039)