On defining numbers of vertex colouring of regular graphs (Q1292860)

From MaRDI portal
Revision as of 20:57, 12 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
On defining numbers of vertex colouring of regular graphs
scientific article

    Statements

    On defining numbers of vertex colouring of regular graphs (English)
    0 references
    0 references
    3 November 1999
    0 references
    In a given graph \(G\), a set of vertices \(S\) with an assignment of colours to them is called a defining set of the vertex colouring of \(G\), if there exists a unique extension of the colours of \(S\) to a \(\chi (G)\)-colouring of the vertices of \(G\), \(\chi (G)\) being the chromatic number of \(G\). A defining set with minimum cardinality is called a minimum defining set (of a vertex colouring) and its cardinality is the defining number, denoted by \(d(G,\chi)\). Among other results, the exact value of \(d(n,r,\chi =r)\), the minimum defining number of all \(r\)-regular \(r\)-chromatic graphs of order \(n\) is determined for some small values of \(r\). Namely for \(r=3,4\), and 5 we have \(d(n,r,\chi =r)=\lfloor ((r-2)(n+ r-3)+2)/(2(r-1))\rfloor \), except possibly for \((n,r)=(10,5)\).
    0 references
    0 references
    regular graph
    0 references
    colouring
    0 references
    defining set
    0 references
    defining number
    0 references

    Identifiers