An identifying open code of a graph G is a set S of vertices that is both a separating open code (that is, NG(u)∩S≠NG(v)∩S for all distinct vertices u and v in G) and a total dominating set (that is, N(v)∩S≠0̸ for all vertices v in G). Such a set exists if and only if the graph G is open twin-free and isolate-free; and the minimum cardinality of an identifying open code in an open twin-free and isolate-free graph G, its identifying open code number, is denoted by γIOC(G). We study the identifying open code number of a graph, in relation with its order and its maximum degree. For Δ a fixed integer at least 3, we show that if G is a connected graph of order n≥5 that contains no 4-cycle and is open twin-free with maximum degree bounded above by Δ, then γIOC(G)≤2Δ−12Δn, unless G is obtained from a star K1,Δ by subdividing every edge exactly once. Moreover, we show that the bound is best possible by constructing graphs that reach the bound when Δ=3, and nearly best possible by another construction when Δ≥4, with identifying open code numbers 2Δ−42Δ−3n.

An identifying code of a closed-twin-free graph G is a dominating set S of vertices of G such that any two vertices in G have a distinct intersection between their closed neighborhoods and S. It was conjectured that there exists an absolute constant c such that for every connected graph G of order n and maximum degree Δ, the graph G admits an identifying code of size at most ([Formula presented])n+c. We provide significant support for this conjecture by exactly characterizing every tree requiring a positive constant c together with the exact value of the constant. Hence, proving the conjecture for trees. For Δ=2 (the graph is a path or a cycle), it is long known that c=3/2 suffices. For trees, for each Δ≥3, we show that c=1/Δ≤1/3 suffices and that c is required to have a positive value only for a finite number of trees. In particular, for Δ=3, there are 12 trees with a positive constant c and, for each Δ≥4, the only tree with positive constant c is the Δ-star. Our proof is based on induction and utilizes recent results from Foucaud and Lehtilä (2022) [17]. We remark that there are infinitely many trees for which the bound is tight when Δ=3; for every Δ≥4, we construct an infinite family of trees of order n with identification number very close to the bound, namely ([Formula presented]. Furthermore, we also give a new tight upper bound for identification number on trees by showing that the sum of the domination and identification numbers of any tree T is at most its number of vertices.

A domination-based identification problem on a graph G is one where the objective is to choose a subset C of the vertex set of G such that C has both, a domination property, that is, C is either a dominating or a total-dominating set of G, and a separation property, that is, any two distinct vertices of G must have distinct closed or open neighborhoods in C. Such a set C is often referred to as a code in the literature of identification problems. In this article, we introduce a new separation property, called full-separation, as it combines aspects of the two well-studied properties of closed- and open-separation. We study it in combination with both domination and total-domination and call the resulting codes full-separating dominating codes (or FD-codes for short) and full-separating total-dominating codes (or FTD-codes for short), respectively. Incidentally, FTD-codes have also been introduced in the literature of identification problems under the name of strongly identifying codes (or SID-codes for short) and under a differently formulated definition. In this paper, we address the conditions for the existence of FD- and FTD-codes, bounds for their size, their relation to codes of the other types and present some extremal cases for these bounds and relations. We further show that the problems of determining an FD- or an FTD-code of minimum cardinality in a graph are NP-hard. We also show that the cardinalities of minimum FD- and FTD-codes of any graph differ by at most one, but that it is NP-hard to decide whether or not they are equal for a given graph in general.

A set S of vertices in a graph G is a dominating set of G if every vertex not in S has a neighbor in S, where two vertices are neighbors if they are adjacent. The domination number, γ(G), of G is the minimum cardinality among all dominating sets of G. Given a set S of vertices of a graph G, two vertices are located by S if they have distinct sets of neighbors in S. Moreover, if S locates every pair of vertices not in S, then it is called a locating set of G. A locating dominating set of G is both a dominating and a locating set of G. The locating domination number, γLD(G), is the minimum cardinality among all locating dominating sets of G. A notable conjecture in the study of locating dominating sets is to show that the locating domination number of an isolate-free and twin-free graph G of order n is at most (Formula Presented). So far, the best approximation to this (Formula Presented)-upper bound conjecture is known to be (Formula Presented). In fact, much in line with the conjecture, an even stronger reformulation proposed in the literature is to ask if it is possible to partition the vertex set of an isolate-free and twin-free graph into two locating sets. However, such partitions into locating sets may not exist if the graph is also allowed to have twins. Continuing with this line of research, we show that if G is an isolate-free (and not necessarily twin-free) graph, then the vertex set of G can be partitioned into a dominating set and a locating dominating set. As a consequence, we infer that every isolate-free graph G of order n satisfies γ(G) + γLD(G) ⩽ n, and we show that the last bound is tight. Moreover, our proof of the existence of a partition of the vertex set of an isolate-free graph into a dominating and a locating dominating set also provides a polynomial-time algorithm to construct such a partition.

Pharmaceuticals play a critical role in both the prevention and treatment of diseases. However, the drug development process is often lengthy, complex, and unpredictable, despite the growing demand for novel and effective treatments. To streamline this process, there is a pressing need for virtual in-silico screening frameworks that can reduce computation time, minimize the selection of non-viable compounds, and improve the accuracy of potential drug candidates. This framework is based on the hypothesis that low binding free energy is a key indicator of a compound's ability to function as an effective inhibitor for a specific target protein. By focusing on this metric, we aim to efficiently classify compounds with high therapeutic potential while eliminating those with less favorable profiles. Our study focuses on the Sirtuin6 protein, a member of the class-III histone deacetylase enzyme family. Sirtuin6 is critical for regulating a wide range of biological processes, including transcription, cell survival, and the de-acylation of proteins such as histones and transcription factors. Given its role in longevity and metabolic regulation, Sirtuin6 is an attractive target for drug development. To enhance the efficiency of the virtual screening process, we employ a machine-learning-driven approach utilizing supervised learning algorithms, including Decision Trees, Random Forests, Logistic Regression, and Support Vector Machines (SVM). These models help optimize resource usage, accelerate computational tasks, and improve the selection of novel inhibitors with low binding free energy.

Vertex splitting is a graph modification operation in which a vertex is replaced by multiple vertices such that the union of their neighborhoods equals the neighborhood of the original vertex. We introduce and study vertex splitting as a graph modification operation for transforming graphs into interval graphs. Given a graph G and an integer k, we consider the problem of deciding whether G can be transformed into an interval graph using at most k vertex splits. We prove that this problem is NP-hard, even when the input is restricted to subcubic planar bipartite graphs. We further observe that vertex splitting differs fundamentally from vertex and edge deletions as graph modification operations when the objective is to obtain a chordal graph, even for graphs with maximum independent set size at most two. On the positive side, we give a polynomial-time algorithm for transforming, via a minimum number of vertex splits, a given graph into a disjoint union of paths, and that splitting triangle free graphs into unit interval graphs is also solvable in polynomial time.

An identifying code of a closed-twin-free graph (Formula presented.) is a set (Formula presented.) of vertices of (Formula presented.) such that any two vertices in (Formula presented.) have a distinct, nonempty intersection between their closed neighborhood and (Formula presented.). It was conjectured that there exists a constant (Formula presented.) such that for every connected closed-twin-free graph (Formula presented.) of order (Formula presented.) and maximum degree (Formula presented.), the graph (Formula presented.) admits an identifying code of size at most (Formula presented.). In [D. Chakraborty, F. Foucaud, M. A. Henning, and T. Lehtilä. Identifying codes in graphs of given maximum degree: Characterizing trees. Discrete Mathematics 349(2), 114826, 2026], we proved the conjecture for all trees. In this article, we show that the conjecture holds for all triangle-free graphs, with the same list of exceptional graphs needing (Formula presented.) as for trees: for (Formula presented.) suffices and there is only a set of 12 trees requiring (Formula presented.) for (Formula presented.), and when (Formula presented.) this set is reduced to the (Formula presented.) -star only. Our proof is by induction, whose starting point is the above result for trees. Along the way, we prove a generalized version of Bondy's theorem on induced subsets [J. A. Bondy. Induced subsets. Journal of Combinatorial Theory, Series B, 1972] that we use as a tool in our proofs. We also use our main result for triangle-free graphs to prove the upper bound (Formula presented.) for graphs that can be made triangle-free by the removal of (Formula presented.) edges.

Using dominating sets to separate vertices of graphs is a well-studied problem in the larger domain of identification problems. In such problems, the objective is to choose a suitable dominating set C of a graph G which is also separating in the sense that the neighborhoods of any two distinct vertices of G have distinct intersections with C. Such a dominating and separating set C of a graph is often referred to as a code in the literature. Depending on the types of dominating and separating sets used, various problems arise under various names in the literature. In this paper, we introduce a new problem in the same realm of identification problems whereby the code, called open-separating dominating code, or OD-code for short, is a dominating set and uses open neighborhoods for separating vertices. The paper studies the fundamental properties concerning the existence, hardness and minimality of OD-codes. Due to the emergence of a close and yet difficult to establish relation of the OD-code with another well-studied code in the literature called open (neighborhood)-locating dominating code (referred to as the open-separating total-dominating code and abbreviated as OTD-code in this paper), we compare the two codes on various graph families. Finally, we also provide an equivalent reformulation of the problem of finding OD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OD-codes, again in relation to OTD-codes of some graph families already studied in this context.

The radio k-chromatic number rck(G) of a graph G is the minimum integer λ such that there exists a function ϕ:V(G)→{0,1,⋯,λ} satisfying |ϕ(u)−ϕ(v)|≥k+1−d(u,v), where d(u,v) denotes the distance between u and v. A considerable amount of attention has been given to find the exact values or providing polynomial time algorithms to determine rck(G) for several basic graph families such as paths, cycles, trees, and powers of paths, usually for some specific values of k. In this article, we find the exact values of rck(G) where G is a power of a path with diameter strictly less than k. Our proof readily provides a linear time algorithm for assigning a radio k-coloring of G. Furthermore, our proof technique is a potential tool for solving the same problem for other classes of graphs having “small” diameters.

In the literature, several identification problems in graphs have been studied, of which, the most widely studied are the ones based on dominating sets as a tool of identification. Hereby, the objective is to separate any two vertices of a graph by their unique neighborhoods in a suitably chosen dominating or total-dominating set. Such a (total-)dominating set endowed with a separation property is often referred to as a code of the graph. In this paper, we study the four separation properties location, closed-separation, open-separation and full-separation. We address the complexity of finding minimum separating sets in a graph and study the interplay of these separation properties with several codes (establishing a particularly close relation between separation and codes based on domination) as well as the interplay of separation and complementation (showing that location and full-separation are the same on a graph and its complement, whereas closed-separation in a graph corresponds to open-separation in its complement).

Several different types of identification problems have been studied in the literature, where the objective is to distinguish any two vertices of a graph by their unique neighborhoods in a suitably chosen dominating or total-dominating set, often referred to as a code. To study such problems under a unifying point of view, reformulations in terms of covering problems in suitably constructed hypergraphs have been provided. Analyzing these hypergraph representations, we introduce a new separation property, called full-separation, which has not yet been considered in the literature so far. We study it in combination with both domination and total-domination, and call the resulting codes full-separating dominating codes (or FD-codes for short) and full-separating total-dominating codes (or FTD-codes for short), respectively. We address the conditions for the existence of FD- and FTD-codes, bounds for their size, their relation to codes of the other types and present some extremal cases for these bounds and relations. We further show that the problems of determining an FD- or an FTD-code of minimum cardinality in a graph is NP-hard. We also show that the cardinalities of minimum FD- and FTD-codes differ by at most one, but that it is NP-hard to decide if they are equal for a given graph in general.

We investigate structural parameterizations for two identification problems in graphs and set systems: Locating-Dominating Set and Test Cover. In the first problem, an input is a graph G and an integer k, and one asks whether there is a subset S of k vertices such that any two distinct vertices not in S are dominated by distinct subsets of S. In the second problem, an input is a set of items U, a collection of subsets F of U called tests, and an integer k, and one asks whether there is a solution set S of at most k tests such that each pair of items belongs to a distinct subset of tests of S. In a related work [ISAAC 2024], we proved that both problems admit a conditional double-exponential lower bound and a matching algorithm when parameterized by the treewidth of the input graph. We continue this line of investigation and consider parameters larger than treewidth, like vertex cover number and feedback edge set number. We design a nontrivial dynamic programming scheme for Test Cover in “slightly super-exponential” time 2O(|U|log|U|)(|U|+|F|)O(1) in the number |U| of items, and also Locating-Dominating Set in time 2O(vclogvc)·nO(1), where vc is the vertex cover number and n the order of the graph. Thus, the known lower bounds with respect to treewidth cannot be extended to the vertex cover number. We also show that when parameterized by the feedback edge set number, Locating Dominating Set admits a linear kernel, answering an open question from [Cappelle et al., LAGOS 2021]. Finally, we show that neither Locating-Dominating Set nor Test Cover is likely to admit a compression algorithm returning an input with a subquadratic number of bits.

A proper k-coloring of a graph G is a neighbor-locating k-coloring if for each pair of vertices in the same color class, the two sets of colors found in their respective neighborhoods are different. The neighbor-locating chromatic number χNL(G) is the minimum k for which G admits a neighbor-locating k-coloring. A proper k-vertex-coloring of a graph G is a locating k-coloring if for each pair of vertices x and y in the same color-class, there exists a color class Si such that d(x,Si)≠d(y,Si). The locating chromatic number χL(G) is the minimum k for which G admits a locating k-coloring. Our main results concern the largest possible order of a sparse graph of given neighbor-locating chromatic number. More precisely, we prove that if a connected graph G has order n, neighbor-locating chromatic number k and average degree d, then n is upper-bounded by O(d2k⌈d⌉+1). We also design a family of graphs of bounded maximum degree whose order is close to reaching this upper bound. Our upper bound generalizes two previous bounds from the literature, which were obtained for graphs of bounded maximum degree and graphs of bounded cycle rank, respectively. Also, we prove that determining whether χL(G)≤k and χNL(G)≤k are NP-complete for sparse graphs: more precisely, for graphs with average degree at most 7, maximum average degree at most 20 and that are 4-partite. We also study the possible relation between the ordinary chromatic number, the locating chromatic number and the neighbor-locating chromatic number of a graph.

We consider the following variants of the classical minimum dominating set problem in graphs: locating-dominating set, locating total-dominating set and open locating-dominating set. All these problems are known to be hard for general graphs. A typical line of attack, therefore, is to either determine the minimum cardinalities of such sets in general or to establish bounds on these minimum cardinalities in special graph classes. In this paper, we study the minimum cardinalities of these variants of the dominating set under a graph operation defined by Mycielski in [21] and is called the Mycielski construction. We provide some general lower and upper bounds on the minimum sizes of the studied sets under the Mycielski construction. We apply the Mycielski construction to stars, paths and cycles in particular, and provide lower and upper bounds on the minimum cardinalities of such sets in these graph classes. Our results either improve or attain the general known upper bounds.

The steep uprise of the incognito cryptocurrency transactions has significantly raised the chances for the ransomware developers of demanding ransom by enciphering sensitive data of not only the individuals but also the large corporate houses. Majority of the recent ransomware operators prefer bitcoin to be a medium of their murky transactions. Although these bitcoin postings are permanently documented in the blockchain ledger, existing practices to detect & mine the origin of these ransomwares are still very difficult, which consist of numerous data gathering steps – making the process much lengthy & complex. As a solution to that, multiple statistical tools machine learning algorithms like Decision Tree, Random Forest, Binomial & Multinomial Logistic Regression has been utilized and a framework has been suggested to detect malicious addresses automatically with a considerably low lead time, by capturing the input data from coin movement topology while leveraging the graph theory & network analysis methodologies as its foundation.

Using dominating sets to separate vertices of graphs is a well-studied problem in the larger domain of identification problems. In such problems, the objective is to choose a suitable dominating set C of a graph G such that the neighbourhoods of all vertices of G have distinct intersections with C. Such a dominating and separating set C is often referred to as a code in the literature. Depending on the types of dominating and separating sets used, various problems arise under various names in the literature. In this paper, we introduce a new problem in the same realm of identification problems whereby the code, called open-separating dominating code, or OSD-code for short, is a dominating set and uses open neighbourhoods for separating vertices. The paper studies the fundamental properties concerning the existence, hardness and minimality of OSD-codes. Due to the emergence of a close and yet difficult to establish relation of the OSD-codes with another well-studied code in the literature called open locating dominating codes, or OLD-codes for short, we compare the two on various graph families. Finally, we also provide an equivalent reformulation of the problem of finding OSD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OSD-codes, again in relation to OLD-codes of some graph families already studied in this context.

The problems of determining the minimum-sized identifying, locating-dominating and open locating-dominating codes of an input graph are special search problems that are challenging from both theoretical and computational viewpoints. In these problems, one selects a dominating set C of a graph G such that the vertices of a chosen subset of V(G) (i.e. either V(G) C or V(G) itself) are uniquely determined by their neighborhoods in C. A typical line of attack for these problems is to determine tight bounds for the minimum codes in various graph classes. In this work, we present tight lower and upper bounds for all three types of codes for block graphs (i.e. diamond-free chordal graphs). Our bounds are in terms of the number of maximal cliques (or blocks) of a block graph and the order of the graph. Two of our upper bounds verify conjectures from the literature with one of them being now proven for block graphs in this article. As for the lower bounds, we prove them to be linear in terms of both the number of blocks and the order of the block graph. We provide examples of families of block graphs whose minimum codes attain these bounds, thus showing each bound to be tight.

We study upper bounds on the size of optimum locating-total dominating sets in graphs. A set S of vertices of a graph G is a locating-total dominating set if every vertex of G has a neighbor in S, and if any two vertices outside S have distinct neighborhoods within S. The smallest size of such a set is denoted by γtL(G). It has been conjectured that γtL(G)≤[Formula presented] holds for every twin-free graph G of order n without isolated vertices. We prove that the conjecture holds for cobipartite graphs, split graphs, block graphs and subcubic graphs.

Foucaud et al. [ICALP 2024] demonstrated that some problems in NP can admit (tight) double-exponential lower bounds when parameterized by treewidth or vertex cover number. They showed these first-of-their-kind results by proving conditional lower bounds for certain graph problems, in particular, the metric-based identification problems (Strong) Metric Dimension. We continue this line of research and highlight the usefulness of this type of problems, to prove relatively rare types of (tight) lower bounds. We investigate fine-grained algorithmic aspects of classical (non-metric based) identification problems in graphs, namely Locating-Dominating Set, and in set systems, namely Test Cover. In the first problem, an input is a graph G on n vertices and an integer k, and the objective is to decide whether there is a subset S of k vertices such that any two distinct vertices not in S are dominated by distinct subsets of S. In the second problem, an input is a set of items U, a collection of subsets F of U called tests, and an integer k, and the objective is to select a set S of at most k tests such that any two distinct items are contained in a distinct subset of tests of S. For our first result, we adapt the techniques introduced by Foucaud et al. [ICALP 2024] to prove similar (tight) lower bounds for these two problems. Locating-Dominating Set (respectively, Test Cover) parameterized by the treewidth of the input graph (respectively, the natural auxiliary graph) does not admit an algorithm running in time 22o(tw) · poly(n) (respectively, 22o(tw) · poly(|U| + |F|))), unless the ETH fails. This augments the short list of NP-Complete problems that admit tight double-exponential lower bounds when parameterized by treewidth, and shows that “local” (non-metric-based) problems can also admit such bounds. We show that these lower bounds are tight by designing treewidth-based dynamic programming schemes with matching running times. Next, we prove that these two problems also admit “exotic” (and tight) lower bounds, when parameterized by the solution size k. We prove that unless the ETH fails, Locating-Dominating Set does not admit an algorithm running in time 2o(k2) · poly(n), nor a polynomial-time kernelization algorithm that reduces the solution size and outputs a kernel with 2o(k) vertices, and Test Cover does not admit an algorithm running in time 22o(k) · poly(|U| + |F|) nor a kernel with 22o(k) vertices. Again, we show that these lower bounds are tight by designing (kernelization) algorithms with matching running times. To the best of our knowledge, Locating-Dominating Set is the first known problem which is FPT when parameterized by solution size k, where the optimal running time has a quadratic function in the exponent. These results also extend the (very) small list of problems that admit an ETH-based lower bound on the number of vertices in a kernel, and (for Test Cover) a double-exponential lower bound when parameterized by the solution size. Whereas it is the first example, to the best of our knowledge, that admit a double exponential lower bound for the number of vertices.

An (m,n)-colored mixed graph, or simply, an (m,n)-graph is a graph having m different types of arcs and n different types of edges. A homomorphism of an (m,n)-graph G to another (m,n)-graph H is a vertex mapping that preserves adjacency; and the type and direction of the adjacency. An (m,n)-relative clique of G is a vertex subset R whose images are always distinct under any homomorphism of G to any H. The maximum cardinality of an (m,n)-relative clique of a graph is called the (m,n)-relative clique number of the graph. In this article, we explore the (m,n)-relative clique numbers for three different families of graphs, namely, graphs having bounded maximum degree Δ, subcubic graphs, partial 2-trees and planar graphs and provide tight or close bounds in most cases.

Given a graph G and an integer k, the objective of the Π -Contraction problem is to check whether there exists at most k edges in G such that contracting them in G results in a graph satisfying the property Π. We investigate the problem where Π is ‘H-free’ (without any induced copies of H). It is trivial that H -free Contraction is polynomial-time solvable if H is a complete graph of at most two vertices. We prove that, in all other cases, the problem is NP-complete. We then investigate the fixed-parameter tractability of these problems. We prove that whenever H is a tree, except for seven trees, H -free Contraction is W[2]-hard. This result along with the known results leaves behind only three unknown cases among trees.

An identifying code of a closed-twin-free graph G is a set S of vertices of G such that any two vertices in G have a distinct intersection between their closed neighborhoods and S. It was conjectured in [F. Foucaud, R. Klasing, A. Kosowski, A. Raspaud. On the size of identifying codes in triangle-free graphs. Discrete Applied Mathematics, 2012] that there exists an absolute constant c such that for every connected graph G of order n and maximum degree, G admits an identifying code of size at most -1/ n + c. We provide significant support for this conjecture by proving it for the class of all bipartite graphs that do not contain any pairs of open-twins of degree at least 2. In particular, this class of bipartite graphs contains all trees and more generally, all bipartite graphs without 4-cycles. Moreover, our proof allows us to precisely determine the constant c for the considered class, and the list of graphs needing c ≥ 0. For = 2 (the graph is a path or a cycle), it is long known that c = 3/2 suffices. For connected graphs in the considered graph class, for each ≥ 3, we show that c = 1/ ≤ 1/3 suffices and that c is required to be positive only for a finite number of trees. In particular, for = 3, there are 12 trees with diameter at most 6 with a positive constant c and, for each ≥ 4, the only tree with positive constant c is the -star. Our proof is based on induction and utilizes recent results from [F. Foucaud, T. Lehtilä. Revisiting and improving upper bounds for identifying codes. SIAM Journal on Discrete Mathematics, 2022].

The problems of determining the minimum-sized identifying, locating-dominating and open locating-dominating codes of an input graph are special search problems that are challenging from both theoretical and computational viewpoints. In these problems, one selects a dominating set C of a graph G such that the vertices of a chosen subset of V(G) (i.e. either V(G) C or V(G) itself) are uniquely determined by their neighborhoods in C. A typical line of attack for these problems is to determine tight bounds for the minimum codes in various graph classes. In this work, we present tight lower and upper bounds for all three types of codes for block graphs (i.e. diamond-free chordal graphs). Our bounds are in terms of the number of maximal cliques (or blocks) of a block graph and the order of the graph. Two of our upper bounds verify conjectures from the literature - with one of them being now proven for block graphs in this article. As for the lower bounds, we prove them to be linear in terms of both the number of blocks and the order of the block graph. We provide examples of families of block graphs whose minimum codes attain these bounds, thus showing each bound to be tight.

The radio k-chromatic number rck(G) of a graph G is the minimum integer λ such that there exists a function ϕ: V(G) → { 0, 1, ⋯, λ} satisfying | ϕ(u) - ϕ(v) | ≥ k+ 1 - d(u, v), where d(u, v) denotes the distance between u and v. To date, several upper and lower bounds of rck(· ) is established for different graph families. One of the most notable works in this domain is due to Liu and Zhu [SIAM Journal on Discrete Mathematics 2005] whose main results were computing the exact values of rck(· ) for paths and cycles for the specific case when k is equal to the diameter. In this article, we find the exact values of rck(G) for powers of paths where the diameter of the graph is strictly less than k. Our proof readily provides a linear time algorithm for providing such labeling. Furthermore, our proof technique is a potential tool for solving the same problem for other graph classes with “small” diameter.

A proper k-vertex-coloring of a graph G is a neighbor-locating k-coloring if for each pair of vertices in the same color class, the sets of colors found in their neighborhoods are different. The neighbor-locating chromatic number χNL(G) is the minimum k for which G admits a neighbor-locating k-coloring. A proper k-vertex-coloring of a graph G is a locating k-coloring if for each pair of vertices x and y in the same color-class, there exists a color class Si such that d(x, Si) ≠ d(y, Si). The locating chromatic number χL(G) is the minimum k for which G admits a locating k-coloring. It follows that χ(G) ≤ χL(G) ≤ χNL(G) for any graph G, where χ(G) is the usual chromatic number of G. We show that for any three integers p, q, r with 2 ≤ p≤ q≤ r (except when 2 = p= q< r ), there exists a connected graph Gp,q,r with χ(Gp,q,r) = p, χL(Gp,q,r) = q and χNL(Gp,q,r) = r. We also show that the locating chromatic number (resp., neighbor-locating chromatic number) of an induced subgraph of a graph G can be arbitrarily larger than that of G. Alcon et al. showed that the number n of vertices of G is bounded above by k(2 k-1- 1 ), where χNL(G) = k and G is connected (this bound is tight). When G has maximum degree Δ, they also showed that a smaller upper-bound on n of order kΔ+1 holds. We generalize the latter by proving that if G has order n and at most an+ b edges, then n is upper-bounded by a bound of the order of k2a+1+ 2 b. Moreover, we describe constructions of such graphs which are close to reaching the bound.