On line colorings of finite projective spaces
A \textit{colouring} of a finite linear space \(S\) is an assignment of the lines of S to a set of colours, say \([k]=\{1,2,\ldots,k\}\). A colouring of \(S\) is called \textit{proper} if any two intersecting lines have a different color, while a colouring is called \textit{complete} if each pair of colours appears on at least one point of \(S\). The \textit{chromatic index} \(\chi'(S)\) is the smallest \(k\) such that there exists a proper colouring with \(k\) colours, the \textit{achromatic index} \(\alpha'(S)\) is the largest \(k\) such that there exists a proper and complete colouring with \(k\) colours, and the \textit{pseudoachromatic index} \(\phi'(S)\) is the largest \(k\) such that there exist a complete (not necessarily proper) colouring with \(k\) colours. It is clear that \(\chi'(S)\leq \alpha'(S)\leq \psi'(S)\) and it is also not too hard to deduce that for \(S=\mathrm{PG}(2,q)\), \(\chi'(S)= \alpha'(S)= \psi'(S)=q^2+q+1\). At present, these values are not known for \(\mathrm{PG}(n,q)\), \(n\geq 3\). In this paper, the authors contribute to this study by showing the following:, where \(\theta_n\) denotes the number of points in \(\mathrm{PG}(n,q)\). They show that for \(n=3.2^i-1\), \(i>0\), \(\alpha'(S)>c_n\frac{1}{q}\theta_n^{\frac{4}{3}+\frac{1}{3n}}\) where \(\frac{1}{2^{7/5}}<c_n<\frac{1}{2^{4/3}}\) is a constant depending only on \(n\). Furthermore, \(\psi'(S)<\frac{1}{q}\theta_n^{3/2}\) for all \(n\geq 2\). The proof of the first statement hinges on the construction of a particular geometric \(2^i-1\)-spread while the proof of the second statement is an easy counting argument. Finally, the authors study the case \(\mathrm{PG}(3,2)\) in detail and provide a quite intricate computer-free proof of the fact that \(\psi'(\mathrm{PG}(3,2))=18\).
- A note on Erdős-Faber-Lovász conjecture and edge coloring of complete graphs.
- A note on the Erdős-Faber-Lovász conjecture: quasigroups and complete digraphs.
- Greedy Colourings of Steiner Triple Systems
- scientific article; zbMATH DE number 124522 (Why is no real title available?)
- scientific article; zbMATH DE number 3523543 (Why is no real title available?)
- scientific article; zbMATH DE number 3627213 (Why is no real title available?)
- scientific article; zbMATH DE number 1101474 (Why is no real title available?)
- scientific article; zbMATH DE number 3298599 (Why is no real title available?)
- scientific article; zbMATH DE number 3328019 (Why is no real title available?)
- scientific article; zbMATH DE number 3334007 (Why is no real title available?)
- On parallelisms in finite projective spaces
- On the chromatic index of a finite projective space
- On the combinatorial problems which I would most like to see solved
- On the edge achromatic numbers of complete graphs
- On the pseudoachromatic index of the complete graph
- On the pseudoachromatic index of the complete graph. II
- On the pseudoachromatic index of the complete graph. III
- Partitioning the planes of \(AG_{2m}(2)\) into 2-designs
- Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane
- On colorings of finite projective planes
- Colouring finite incidence structures
- On the balanced upper chromatic number of finite projective planes
- On the balanced upper chromatic number of cyclic projective planes and projective spaces
- Some new characterizations of graph colorability and of blocking sets of projective spaces
- On chromatic indices of finite affine spaces
- The chromatic index of finite projective spaces
- On the harmonious chromatic number of graphs
- On perfect balanced rainbow-free colorings and complete colorings of projective spaces
- Banff designs: difference methods for coloring incidence graphs
- Legitimate colorings of projective planes
- On the chromatic index of a finite projective space
This page was built for publication: On line colorings of finite projective spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2045382)
