Internat. J. Math. & Math Si.
Vol. 5 No. 4 (1982) 823-825
823
THE CHROMATIC INDEX OF CYCLIC STEINER 2-DESIGNS
CHARLES J. COLBOURN and MARLENE J. COLBOURN
Department of Computational Science University of Saskatchewan
Saskatoon, CANADA S7N OW0 (Received May 25, 1981)
ABSTRACT. The number of colors needed to colour the blocks of a cyclic Steiner 2- design S(2, k, v) is at most v.
KEY WORDS AND PHRASES. Block design, Steiner system, coloing, chromatic index.
1980 MATHEMATICS SUBJECT CLASSIFICATION CODES. 05B05, 05B10.
i. INTRODUCTION.
A Stelner 2-deslgn S(2, k, v) is a pair (V, B); V is a v-set of elements and B is a collection of k-subsets of V called blocks. Each 2-subset of V appears in pre- cisely one block. A colour class in a Steiner system is a set of palrwlse disjoint blocks. A k-block colourlng of (V, B) is a partitioning of B into k colour classes.
The chromatic index of a Stelner system is the least k for which a k-block colourlng exists.
Stelner systems with small chromatic index have been studied under the guise of resolvable or nearly resolvable designs (see [1,2] and references therein). Often Steiner and related systems are employed in the scheduling of tournaments or experl- ments; in these contexts, small chromatic index corresponds to few "rounds". A question of much concern here is: what is the largest possible number of rounds re- quired for a specified Steiner 2-design S(2, k, v)? In other words, what is the upper bound on the chromatic index of a Steiner 2-deslgn? One weak upper bound is immediate.
LEMMA I: The chromatic index of a Steiner 2-deslgn S(2, k, v) is less thn kv/(k-i).
824 C.J. COLBOURN AND M.J. COLBOURN
PROOF. Given a Steiner system S(2, k, v), construct its block intersection graph as follows. Each block is represented by a vertex; two vertices are adjacent exactly when the corresponding blocks intersect. The chromatic index of a Stelner 2-deslgn is the chromatic number of its block intersection graph. The block inter- section graph has maximum degree less than kv/(k-1). Hence, Brooks’ theorem
[3]
guarantees that the chromatic number is at most kv/(k-l).
We suspect that lemma is quite a weak bound; one reason is that a conjecture of Erds, Faber, and Lovasz
[4]
would ensure an upper bound of v on the chromatic index. The purpose of this note is to show that the chromatic index of a cyclic Stelner system S(2,k,v) is at most v.A Steiner system S(2,k,v) is cyclic if its element set is {0,I v-l} and the mapping i i+l (mod v) is an automorphism. This automorphlsm partitions the blocks of the Stelner system into orbits. Each orbit contains v blocks when v
(mod k(k-l)). When v
-=
k (mod k(k-l)), each orbit except one contains v blocks.The exception, the short orbit, contains v/k blocks. The reader is referred to
[5]
for a detailed survey of cyclic Stelner 2-designs; the simple introduction here suffices to prove
THEOREM 2. A cyclic Stelner system S(2,k,v) has chromatic index at most v.
PROOF. If there is a short orbit of blocks, we use a single colour for all blocks in this orbit, since they are disjoint
[5].
For each "full" orbit of blocks, we consider the subgraph of the block intersection graph induced on this orbit.This subgraph has degree k(k-l). Hence, Brooks’ theorem guarantees that it can be coloured in k(k-l) colours, unless it is composed of (k(k-l)+l)-cllques. Observe that at most one orbit can induce such a graph, and this can only happen when k(k-l)+l divides v. Thus, for v 1 (rood k(k-l)), we need at most v colours, since we have (v-1)/(k(k-l)) full orbits. Similarly, for v k (rood k(k-l)), we have one short orbit, and (v-k)/(k(k-1)) full orbits; hence, at most v-k+2 colours are needed, completing the proof.
Although cyclic systems comprise a very small fraction of all Stelner systems, we believe that the techniques used in theorem 2 are interesting and have general
CHROMATIC INDEX OF CYCLIC STEINER 2-DESIGN 825
applicability. Future research might employ different decompositions of the block intersection graph into manageable pieces, such as the orbits used here, and the colouring of the system "piece by piece".
ACKNOWLEDGEMENTS. Research of the first author is supported in part by NSERC Canada Grant A5047. We would like to thank Rudl Mathon, Eric Mendelsohn, Kevln Phelps, and Alex Rosa for their comments.
REFERENCES
I. HARTMAN, A. Resolvable Designs, M. Sc. thesis, Israel Institute of Technology, Halfa, Israel, June 1978.
2. RAY-CHAUDHURI, D.K., and WILSON, R.M. Solution of Kirkman’s Schoolgirl Problem, Proc. Symp. Pure Math. 19 (Amer. Math. Soc., Providence, RI), 1971.
3. BROOKS, R.L. On Colourlng the Nodes of a Network,. Proc. Cambridge Philos. So____c.
37 (1941) 194-197.
4. ERDOS, P. On the Combinatorial Problems I Would Most Like to See Solved, Comblnatorlca I (1981) 25-42.
5. COLBOURN, M.J., and MATHON, R.A. On Cyclic Stelner 2-deslgns. Annals of Disc.
Math. 7 (1980) 215-253.
Mathematical Problems in Engineering
Special Issue on
Time-Dependent Billiards
Call for Papers
This subject has been extensively studied in the past years for one-, two-, and three-dimensional space. Additionally, such dynamical systems can exhibit a very important and still unexplained phenomenon, called as the Fermi acceleration phenomenon. Basically, the phenomenon of Fermi accelera- tion (FA) is a process in which a classical particle can acquire unbounded energy from collisions with a heavy moving wall.
This phenomenon was originally proposed by Enrico Fermi in 1949 as a possible explanation of the origin of the large energies of the cosmic particles. His original model was then modified and considered under different approaches and using many versions. Moreover, applications of FA have been of a large broad interest in many different fields of science including plasma physics, astrophysics, atomic physics, optics, and time-dependent billiard problems and they are useful for controlling chaos in Engineering and dynamical systems exhibiting chaos (both conservative and dissipative chaos).
We intend to publish in this special issue papers reporting research on time-dependent billiards. The topic includes both conservative and dissipative dynamics. Papers dis- cussing dynamical properties, statistical and mathematical results, stability investigation of the phase space structure, the phenomenon of Fermi acceleration, conditions for having suppression of Fermi acceleration, and computational and numerical methods for exploring these structures and applications are welcome.
To be acceptable for publication in the special issue of Mathematical Problems in Engineering, papers must make significant, original, and correct contributions to one or more of the topics above mentioned. Mathematical papers regarding the topics above are also welcome.
Authors should follow the Mathematical Problems in Engineering manuscript format described at http://www .hindawi.com/journals/mpe/. Prospective authors should submit an electronic copy of their complete manuscript through the journal Manuscript Tracking System athttp://
mts.hindawi.com/according to the following timetable:
Manuscript Due December 1, 2008 First Round of Reviews March 1, 2009 Publication Date June 1, 2009
Guest Editors
Edson Denis Leonel,Departamento de Estatística, Matemática Aplicada e Computação, Instituto de Geociências e Ciências Exatas, Universidade Estadual Paulista, Avenida 24A, 1515 Bela Vista, 13506-700 Rio Claro, SP, Brazil ; [email protected]
Alexander Loskutov,Physics Faculty, Moscow State University, Vorob’evy Gory, Moscow 119992, Russia;
Hindawi Publishing Corporation http://www.hindawi.com
