Explore the vast range of titles available.

We show that there is no simple (e.g. finite or countable) basis for Borel graphs with infinite Borel chromatic number. In fact, it is proved that the closed subgraphs of the shift graph on [N]N with finite (or, equivalently, ≤3) Borel chromatic number form a Σ21-complete set. This answers a question of Kechris and Marks and strengthens several earlier results.

Let G be a simple connected graph. Then, χ L ( G ) and χ D ( G ) will denote the locating chromatic number and the distinguishing chromatic number of G , respectively. In this paper, we investigate a comparison between χ L ( G ) and χ D ( G ) . We prove that χ D ( G ) ≤ χ L ( G ) . Moreover, we determine some types of graphs whose locating and distinguishing chromatic numbers are equal. Specially, we characterize all graphs G of order n with property that χ D ( G ) = χ L ( G ) = k , where k = 3 , n - 2 or n - 1 . In addition, we construct graphs G with χ D ( G ) = n and χ L ( G ) = m for every 4 ≤ n ≤ m .

For a given set M of positive integers, a well-known problem of Motzkin asked to determine the maximal asymptotic density of M-sets, denoted by μ(M), where an M-set is a set of non-negative integers in which no two elements differ by an element in M. In 1973, Cantor and Gordon found μ(M) for |M| ≤ 2. Partial results are known in the case |M| ≥ 3 including results in the case when M is an infinite set. This number theory problem is also related to various types of coloring problems of the distance graphs generated by M. In particular, it is known that the reciprocal of the fractional chromatic number of the distance graph generated by M is equal to the value μ(M) when M is finite. Motivated by the families M = {a, b, a + b} and M = {a, b, a + b, b − a} discussed by Liu and Zhu, we study two families of sets M, namely, M = {a, b, b − a, n(a + b)} and M = {a, b, a + b, n(b − a)}. For both of these families, we find some exact values and some bounds on μ(M). We also find bounds on the fractional and circular chromatic numbers of the distance graphs generated by these families. Furthermore, we determine the exact values of chromatic number of the distance graphs generated by these two families.

We determine irregular set chromatic number of comb, friendship, K-ary tree, n-sunlet, coconut tree and jelly fish graph.

The essential annihilating-ideal graph E G ( R ) of a commutative unital ring R is a simple graph, whose vertices are non-zero ideals of R with non-zero annihilator and there exists an edge between two distinct vertices I ,  J if and only if Ann ( IJ ) has a non-zero intersection with any non-zero ideal of R . In this paper, we show that E G ( R ) is weakly perfect, if R is Noetherian and an explicit formula for the clique number of E G ( R ) is given. Moreover, the structures of all rings whose essential annihilating-ideal graphs have chromatic number 2 are fully determined. Among other results, twin-free clique number and edge chromatic number of E G ( R ) are examined.

The k-independence number of a graph G is the maximum size of a set of vertices at pairwise distance greater than k . In this paper, for each positive integer k , we prove sharp upper bounds for the k -independence number in an n -vertex connected graph with given minimum and maximum degree.

The notion of the b-chromatic number of a graph attracted much research interests and recently a new concept, namely the b-chromatic sum of a graph, denoted by , has also been introduced. Motivated by the studies on b-chromatic sum of graphs, in this paper we introduce certain new parameters such as -chromatic sum, -chromatic sum, -chromatic sum, -chromatic sum and -chromatic sum of graphs. We also discuss certain results on these parameters for a selection of standard graphs.

It is well known that for any integers k and g , there is a graph with chromatic number at least k and girth at least g . In 1960s, Erdös and Hajnal conjectured that for any k and g , there exists a number h ( k , g ), such that every graph with chromatic number at least h ( k , g ) contains a subgraph with chromatic number at least k and girth at least g . In 1977, Rödl proved the case when$g=4$, for arbitrary k . We prove the fractional chromatic number version of Rödl’s result.

In this paper, a crisp overview is provided about the evolution of the concept of the collaboration graph resulting out of the social networks guided by the academic relation of coauthorship describing Erdos number. We have obtained some general results concerning the collaboration graph that evolves out of modeling the academic relationship among the Rolf Nevanlinna Prize winners based on their Erdos number. In addition, the strong and weak domination numbers and certain coloring numbers are also computed for the collaboration graph.

Let G be a simple, connected and undirected graph. Let r, k be natural numbers. By a proper k-coloring of a graph G, we mean a map c : V (G) → S, where |S| = k, such that any two adjacent vertices receive different colors. An r-dynamic k-coloring is a proper k-coloring c of G such that |c(N(v))| ≥ min{r, d(v)} for each vertex v in V (G), where N(v) is the neighborhood of v and c(S) = {c(v) : v ∈ S} for a vertex subset S. The r-dynamic chromatic number, written as χr(G), is the minimum k such that G has an r-dynamic k-coloring. By simple observation it is easy to see that χr(G) ≤ χr+1(G), however χr+1(G) − χr(G) does not always show a small difference for any r. Thus, finding an exact value of χr(G) is significantly useful. In this paper, we will study some of them especially when G are prism graph, three-cyclical ladder graph, joint graph and circulant graph.