On defining numbers of vertex colouring of regular graphs (Q1292860): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
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 | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(99)90113-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4212769193 / rank | |||
Normal rank |
Latest revision as of 10:41, 30 July 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