Header menu link for other important links
X
A new graph parameter and a construction of larger graph without increasing radio k-chromatic number
Published in Springer New York LLC
2017
Volume: 33
Β Β Β 
Issue: 4
Pages: 1 - 13
Abstract
For a positive integer π‘˜β‰₯2, the radio k-coloring problem is an assignment L of non-negative integers (colors) to the vertices of a finite simple graph G satisfying the condition |𝐿(𝑒)βˆ’πΏ(𝑣)|β‰₯π‘˜+1βˆ’π‘‘(𝑒,𝑣), for any two distinct vertices u, v of G and d(u, v) being distance between u, v. The span of L is the largest integer assigned by L, while 0 is taken as the smallest color. An π‘Ÿπ‘π‘˜-coloring on G is a radio k-coloring on G of minimum span which is referred as the radio k-chromatic number of G and denoted by π‘Ÿπ‘π‘˜(𝐺). An integer h, 0<β„Ž<π‘Ÿπ‘π‘˜(𝐺), is a hole in a π‘Ÿπ‘π‘˜-coloring on G if h is not assigned by it. In this paper, we construct a larger graph from a graph of a certain class by using a combinatorial property associated with (π‘˜βˆ’1) consecutive holes in any π‘Ÿπ‘π‘˜-coloring of a graph. Exploiting the same property, we introduce a new graph parameter, referred as (π‘˜βˆ’1)-hole index of G and denoted by πœŒπ‘˜(𝐺). We also explore several properties of πœŒπ‘˜(𝐺) including its upper bound and relation with the path covering number of the complement 𝐺𝑐.
About the journal
JournalData powered by TypesetJournal of Combinatorial Optimization
PublisherData powered by TypesetSpringer New York LLC
ISSN1382-6905