Set colourings of graphs. (Reprint)
This article is a reprint of an important paper published in Discrete Math. 25, 21--26 (1979; Zbl 0403.05038). An \(r\)-set colouring of a graph \(G\) is an assignment of \(r\) distinct colours to each vertex of \(G\) so that the sets of colours assigned to adjacent vertices are disjoint. We denote by \(\chi^{(r)} (G)\) the minimum number of colours required to \(r\)-set colour \(G\). The set-chromatic number of \(G\), denoted by \(\chi^*(G)\), is defined by \(\chi^* (G) = \inf_r \chi^{(r)} (G) / r\). Clearly \( 2 \leq \chi^* (G) \leq \chi (G)\). By making use of a recent result of L. Lovász we prove that \(\min \{ \chi^{(r)} (G) \;:\;\chi(G) = k \} = 2r + k - 2\) and \(\min \{ \chi^{(r)} (G) \;:\;G\) is uniquely \(k\)-colourable\(\} = 2r + k - 1\). In particular, given any \(k\), \(\chi^*(G)\) may be arbitrarily close to 2, and given any \(r\), the ratio \(\chi^{(r)}(G)/\chi(G)\) may be arbitrarily close to 1, even if \(G\) is uniquely colourable. The results disprove a conjecture of D.P. Geller.
- A (<5)-Colour Theorem for Planar Graphs
- Applications of product colouring
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- r-tuple colorings of uniquely colorable graphs
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- The chromatic number and other functions of the lexicographic product
- Defining sets and uniqueness in graph colorings: A survey
- Chromatic vertex Folkman numbers
- Set colorings of digraphs
- A tight bound on the set chromatic number
- Set colorings in perfect graphs.
- On multiset colorings of graphs
- scientific article; zbMATH DE number 863472 (Why is no real title available?)
- Set-coloring of edges and multigraph Ramsey numbers
This page was built for publication: Set colourings of graphs. (Reprint)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2497995)
