On irreducible no-hole L(2, 1)-coloring of subdivision of graphs

Nibedita Mandal () and Pratima Panigrahi ()
Additional contact information
Nibedita Mandal: Indian Institute of Technology Kharagpur
Pratima Panigrahi: Indian Institute of Technology Kharagpur

Journal of Combinatorial Optimization, 2017, vol. 33, issue 4, No 16, 1442 pages

Abstract: Abstract An L(2, 1)-coloring (or labeling) of a graph G is a mapping $$f:V(G) \rightarrow \mathbb {Z}^{+}\bigcup \{0\}$$ f : V ( G ) → Z + ⋃ { 0 } such that $$|f(u)-f(v)|\ge 2$$ | f ( u ) - f ( v ) | ≥ 2 for all edges uv of G, and $$|f(u)-f(v)|\ge 1$$ | f ( u ) - f ( v ) | ≥ 1 if u and v are at distance two in G. The span of an L(2, 1)-coloring f, denoted by span f, is the largest integer assigned by f to some vertex of the graph. The span of a graph G, denoted by $$\lambda (G)$$ λ ( G ) , is min {span $$f: f\text {is an }L(2,1)\text {-coloring of } G\}$$ f : f is an L ( 2 , 1 ) -coloring of G } . If f is an L(2, 1)-coloring of a graph G with span k then an integer l is a hole in f, if $$l\in (0,k)$$ l ∈ ( 0 , k ) and there is no vertex v in G such that $$f(v)=l$$ f ( v ) = l . A no-hole coloring is defined to be an L(2, 1)-coloring with span k which uses all the colors from $$\{0,1,\ldots ,k\}$$ { 0 , 1 , … , k } , for some integer k not necessarily the span of the graph. An L(2, 1)-coloring is said to be irreducible if colors of no vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring of a graph G, also called inh-coloring of G, is an L(2, 1)-coloring of G which is both irreducible and no-hole. The lower inh-span or simply inh-span of a graph G, denoted by $$\lambda _{inh}(G)$$ λ i n h ( G ) , is defined as $$\lambda _{inh}(G)=\min ~\{$$ λ i n h ( G ) = min { span f : f is an inh-coloring of G}. Given a graph G and a function h from E(G) to $$\mathbb {N}$$ N , the h-subdivision of G, denoted by $$G_{(h)}$$ G ( h ) , is the graph obtained from G by replacing each edge uv in G with a path of length h(uv). In this paper we show that $$G_{(h)}$$ G ( h ) is inh-colorable for $$h(e)\ge 2$$ h ( e ) ≥ 2 , $$e\in E(G)$$ e ∈ E ( G ) , except the case $$\Delta =3$$ Δ = 3 and $$h(e)=2$$ h ( e ) = 2 for at least one edge but not for all. Moreover we find the exact value of $$\lambda _{inh}(G_{(h)})$$ λ i n h ( G ( h ) ) in several cases and give upper bounds of the same in the remaining.

Keywords: L(2; 1)-coloring; No-hole coloring; Irreducible coloring; Span of a graph; Subdivision graph; 05C15 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0047-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:4:d:10.1007_s10878-016-0047-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0047-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().