Zero-sum partition theorems for graphs
type: Item
instance of: scholarly article
title: Zero-sum partition theorems for graphs
zbMATH Open document ID: 0809.05071
DOI: 10.1155/S0161171294000992
author: Yair Caro
author: Ilia Krasikov
author: Yehuda Roditty
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 1995-03-20T00:00:00Z
full work available at URL: https://eudml.org/doc/47104
review text: Let \(\phi(G,k)\) denote the smallest integer \(m\) so that the vertices of the hypergraph \(G\) can be partitioned into \(m\) cells \(V_ 1,\dots, V_ m\) so that for each \(i= 1,\dots, m\), \(e(V_ i)\equiv 0\pmod k\), where \(e(V_ i)\) denotes the number of edges in the subhypergraph induced by \(V_ i\). Clearly \(\phi(G,k)\) is bounded above by the chromatic number of \(G\). This paper is devoted to the proofs of the following three results: Theorem 1. Let \(r, q\geq 2\) be positive integers. (1) There exists a constant \(t(q,r)\), depending only on \(q\) and \(r\), such that \(\phi(H,q)\leq t(q,r)\), for every \(r\)-uniform hypergraph \(H\). (2) If \(r= 2\), \(q= 2^ k\) then \(t(q,2)= 2q- 1\). Theorem 2. If \(r= 2\), \(q= p^ n\), \(p\) an odd prime, then \[ t(q,2)\leq {3\over 2} (q- 1)- {(2(q- 1)- 1)^{{1\over 2}}\over 4}+ {9\over 8}. \] Theorem 3. \(t(3,2)= 3\) and \(4\leq t(5,2)\leq 5\).
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 697110
zbMATH Keywords: zero-sum partition
zbMATH Keywords: hypergraph
zbMATH Keywords: subhypergraph
zbMATH Keywords: chromatic number
reviewed by: Jack E. Graver
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 697110