Colourings of star systems

DOI10.1002/JCD.21712MaRDI QIDQ6146750zbMATH OpenOpenAlexFDO

Authors Iren Darijani, David A. Pike

Publication date 31 January 2024

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.06275

zbMATH Keywords

chromatic numbercolouringdecompositionstar systemunique colouring

Mathematics Subject Classification ID

Other designs, configurations (05B30) Coloring of graphs and hypergraphs (05C15) Graph designs and isomorphic decomposition (05C51)

Abstract: 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 $phi$ 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 $kgeq2$, 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 $egeq3$. We show that for all $kgeq2$ and $egeq3$, there exists a $k$-chromatic $e$-star system of order $n$ for all sufficiently large $n$ such that $nequiv0,1$ (mod $2e$). Finally, we prove that for all $kgeq2$ and $egeq3$, there exists a uniquely $k$-chromatic $e$-star system of order $n$ for all sufficiently large $n$ such that $nequiv0,1$ (mod $2e$).

Recommendations

• Block colourings of star systems
• Star chromatic numbers of hypergraphs and partial Steiner triple systems
• On colourings of Steiner triple systems
• Equitable embeddings of Steiner triple systems
• Coloring 4-cycle systems

Cites work

• Coloring Steiner Triple Systems
• Colouring even cycle systems
• scientific article; zbMATH DE number 3478938 (Why is no real title available?)
• On claw-decomposition of complete graphs and complete bigraphs
• On cycle systems with specified weak chromatic number
• On tree factorizations of K_n
• Uniquely 3-colourable Steiner triple systems

Cited in

(1)

• Colourings of path systems

This page was built for publication: Colourings of star systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6146750)