Premium
Colourings of star systems
Author(s) -
Darijani Iren,
Pike David A.
Publication year - 2020
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21712
Subject(s) - combinatorics , mathematics , star (game theory) , monochromatic color , chromatic scale , existential quantification , vertex (graph theory) , partition (number theory) , bipartite graph , graph , friendship graph , complete graph , discrete mathematics , physics , graph power , line graph , mathematical analysis , optics
An e ‐star is a complete bipartite graph K 1 , e . An e ‐star system of order n > 1 , S e ( n ) , is a partition of the edges of the complete graph K n into e ‐stars. An e ‐star system is said to be k ‐colourable if its vertex set can be partitioned into k sets (called colour classes) such that no e ‐star is monochromatic. The system S e ( n ) is k ‐chromatic if S e ( n ) is k ‐colourable but is not ( k − 1 ) ‐colourable. If every k ‐colouring of an e ‐star system can be obtained from some k ‐colouring ϕ by a permutation of the colours, we say that the system is uniquely k ‐colourable. In this paper, we first show that for any integer k ⩾ 2 , there exists a k ‐chromatic 3‐star system of order n for all sufficiently large admissible n . Next, we generalize this result for e ‐star systems for any e ⩾ 3 . We show that for all k ⩾ 2 and e ⩾ 3 , there exists a k ‐chromatic e ‐star system of order n for all sufficiently large n such that n ≡ 0 , 1 (mod 2 e ). Finally, we prove that for all k ⩾ 2 and e ⩾ 3 , there exists a uniquely k ‐chromatic e ‐star system of order n for all sufficiently large n such that n ≡ 0 , 1 (mod 2 e ).