Vertex partition of hypergraphs and maximum degenerate subhypergraphs

DOI10.5614/EJGTA.2021.9.1.1zbMATH Open1468.05086arXiv1807.02308OpenAlexW3159665602MaRDI QIDQ4958039FDOQ4958039

Authors: Thomas Schweser, Michael Stiebitz 

Publication date: 6 September 2021

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

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.

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

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

zbMATH Keywords

degeneracyvertex partitionhypergraph decompositioncoloring of hypergraphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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)