Sensitivity of r-hued colouring of graphs. Issue 4 (2nd October 2018)

• Record Type: Journal Article
• Authors: Song, Huimin; Miao, Lianying; Miao, Zhengke; Lai, Hong-Jian
• Is Part Of: International journal of computer mathematics. Volume 3:Issue 4(2018)
• Page Start: 262
• Page End: 273
• Publication Date: 2018-10-02
• Subjects: Sensitivity -- r-hued chromatic number -- elementary operations -- dynamic chromatic number -- r-hued colouring; 05C15; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2018.1541931
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: A proper k -colouring c of a graph G is a -colouring if for every vertex v with degree there are at least min different colours present in the neighbourhood of v . The r-hued chromatic number of G, , is the least integer k such that G has a -colouring. We show that, for any, there exist infinitely many graphs G with the property that G contains a subgraph H satisfying . We also determine, for any graph G and any or, the best possible upper and lower bounds of, and those of . We also study the structure of the graphs reaching the optimal bounds.