E-resources
Peer reviewed
-
Lin, Wensong
Discrete Applied Mathematics, 04/2020, Volume: 277Journal Article
Let G be a simple graph. Suppose f is a mapping from V(G) to nonnegative integers. If, for any two adjacent vertices u and v of G, |f(u)−f(v)|≥2, then f is called a 2-distant coloring of G. In this paper, we introduce a relaxation of 2-distant coloring of a graph. Let t be a nonnegative integer. Suppose f is a mapping from V(G) to nonnegative integers. If adjacent vertices receive different integers and for each vertex u of G, the number of neighbors v of u with |f(v)−f(u)|=1 is at most t, then f is called a t-relaxed 2-distant coloring of G. If t=0 then f is just a 2-distant coloring of G. The span of f, denote by sp(f), is the difference between the maximum and minimum integers used by f. The minimum span of a t-relaxed 2-distant coloring of G, is called t-relaxed 2-distant coloring span of G, denoted by sp2t(G). Suppose G is a graph. Let γ:V(G)→Z+ be a function defined on V(G). A γ-relaxed 2-distant coloring of G with span k is a mapping f from V(G) to {0,1,…,k} such that f(u)≠f(v) for any two adjacent vertices u and v and each vertex u of G has at most γ(u) neighbors v with |f(v)−f(u)|=1. In this paper, we prove that, for any two positive integers t and k with k≥2, deciding if sp2t(G)≤k for a graph G is NP-complete, except the case when t=1 and k=2 which is polynomial-time solvable. Let t be any nonnegative integer. It is easy to see that sp2t(G)≤6 for any planar graph G and sp2t(G)≤4 for any outerplanar graph G. We prove that, for any two positive integers t and k with k∈{2,3,4,5}, deciding if sp2t(G)≤k for a planar graph G is NP-complete, except the case when t=1 and k=2 which is polynomial-time solvable. We present examples to illustrate that there is no constant integer t such that every planar graph has a t-relaxed 2-distant coloring of span 5 and there is no constant integer t such that every outerplanar graph has a t-relaxed 2-distant coloring of span 3. We introduce pseudo ear decomposition and simple pseudo ear decomposition of a graph and show that a graph is outerplanar if and only if it admits a simple pseudo ear decomposition. Using this result, we show that each outerplanar graph has a γ-relaxed 2-distant coloring with span 3, where γ(v)=⌈d(v)2⌉ for each vertex v of G and the function γ is sharp in some sense, and that every triangle-free outerplanar graph has a 1-relaxed 2-distant coloring with span 3.
Author
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.