On defining numbers of vertex colouring of regular graphs (Q1292860): Difference between revisions
From MaRDI portal
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
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
regular graph
0 references
colouring
0 references
defining set
0 references
defining number
0 references