On defining numbers of vertex colouring of regular graphs (Q1292860): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Q4017176 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4386307 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2761069 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Defining sets in vertex colorings of graphs and latin rectangles / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4552244 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4018557 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4858978 / rank
 
Normal rank

Revision as of 20:36, 28 May 2024

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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers