ARTICLE
TITLE

Vertex partition of hypergraphs and maximum degenerate subhypergraphs

SUMMARY

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.

PAGES
pp. 1 - 9

 Articles related

Debi Oktia Haryeni,Edy Tri Baskoro,Suhadi Wido Saputro    

For a graph G=(V,E), a partition O={O1,O2,…,Ok} of the vertex set V is called a resolving partition if every pair of vertices u,v ? V(G) have distinct representations under O. The partition dimension of G is the minimum integer k such that G has a resolv... see more


Niranjan Balachandran, Deepanshu Kush    

A bipartite graph G(X,Y,E)G(X,Y,E) with vertex partition (X,Y)(X,Y) is said to have the Normalized Matching Property (NMP) if for any subset S?XS\subseteq X we have |N(S)||Y|=|S||X|\frac{|N(S)|}{|Y|}\geq\frac{|S|}{|X|}. In this paper, we prove the follow... see more


Teng Fang, Xin Gui Fang, Binzhou Xia, Sanming Zhou    

A finite graph G\Gamma is GG-symmetric if it admits GG as a group of automorphisms acting transitively on V(G)V(\Gamma) and transitively on the set of ordered pairs of adjacent vertices of G\Gamma. If V(G)V(\Gamma) admits a nontrivial GG-invariant partit... see more


V. R. Girish,P. Usha    

A set D - V is a dominating set of G if every vertex in V - D is adjacent to some vertex in D. The dominating number ?(G) of G is the minimum cardinality of a dominating set D. A dominating set D of a graph G = (V;E) is a split dominating set i... see more


Dian Kastika Syofyan,Edy Tri Baskoro,Hilda Assiyatun    

The investigation on the locating-chromatic number of a graph was initiated by Chartrand et al. (2002). This concept is in fact a special case of the partition dimension of a graph. This topic has received much attention. However, the results a... see more