A lower bound technique for radio \(k\)-coloring

DOI10.1016/j.disc.2016.12.021zbMath1357.05040OpenAlexW2587361194MaRDI QIDQ512555

Sandip Das, Sagnik Sen, Sasthi C. Ghosh, Soumen Nandi

Publication date: 27 February 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2016.12.021

zbMATH Keywords

pathsapproximation algorithmradio \(k\)-coloringlower bound techniqueregular grid graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

On the radio \(k\)-chromatic number of some classes of trees ⋮ On radio \(k\)-labeling of the power of the infinite path ⋮ A linear algorithm for radio \(k\)-coloring powers of paths having small diameter ⋮ Unnamed Item ⋮ Optimal radio labellings of block graphs and line graphs of trees ⋮ Antipodal number of full \(m\)-ary trees ⋮ On the radio number for corona of paths and cycles ⋮ Upper bound for radio -chromatic number of graphs in connection with partition of vertex set ⋮ Antipodal radio labelling of full binary trees ⋮ Radio \(k\)-chromatic number of full \(m\)-ary trees ⋮ Relationship between radio k-chromatic number of graphs and square graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On \(L(k, k - 1, \ldots, 1)\) labeling of triangular lattice
• A lower bound for radio \(k\)-chromatic number
• A survey on radio \(k\)-colorings of graphs
• Optimal radio labellings of complete \(m\)-ary trees
• Nearly antipodal chromatic number $ac'(P_n)$ of the path $P_n$
• Labelling Graphs with a Condition at Distance 2
• Radio k-colorings of paths
• The $L(2,1)$-Labeling Problem on Graphs
• Linear and cyclic radio k-labelings of trees
• Multilevel Distance Labelings for Paths and Cycles

This page was built for publication: A lower bound technique for radio \(k\)-coloring