Premium
Problems in Zero‐Sum Combinatorics
Author(s) -
Caro Yair
Publication year - 1997
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610797005152
Subject(s) - combinatorics , mathematics , partition (number theory) , vertex (graph theory) , zero (linguistics) , graph , discrete mathematics , algebraic number , prime power , integer (computer science) , algebraic combinatorics , prime (order theory) , computer science , mathematical analysis , philosophy , linguistics , programming language
Let t ( G , q ) denote the smallest integer t such that the vertex set V of the graph G can be partitioned into t classes V ( G )=⋓ t i =1 V i such that the number of edges in the induced subgraph 〈 V i 〉 for 1⩽ i ⩽ t , is divisible by q . Using an algebraic theorem due to Baker and Schmidt we prove that if q is a prime power then t ( G , q ) can be computed and a corresponding partition can be presented in a polynomial time.