Sharif Digital Repository

A graph G is called an Mr(k)-graph if G has no k-list assignment to its vertices with exactly r vertex colorings. We characterize all A 3(2)-graphs. More precisely, it is shown that a connected graph G is an A3(2)-graph if and only if each block of G is a complete graph with at least three vertices  

Let (Formula presented.) be a graph. A vertex coloring (Formula presented.) of (Formula presented.) is called (Formula presented.)-vertex coloring if (Formula presented.) for every vertex (Formula presented.) of (Formula presented.), where (Formula presented.) is the set of colors of vertices adjacent to (Formula presented.). Let (Formula presented.) be the maximum number of colors used in an (Formula presented.)-vertex coloring of (Formula presented.). We provide some lower and upper bounds for (Formula presented.) in terms of girth, diameter or size of (Formula presented.). Also, for every tree (Formula presented.), we obtain (Formula presented.). © 2018 World Scientific Publishing Company... 

Let G be a graph. A vertex coloring ψ of G is called N2-vertex coloring if |ψ(v)|≤ 2 for every vertex v of G, where ψ(v) is the set of colors of vertices adjacent to v. Let t2(G) be the maximum number of colors used in an N2-vertex coloring of G. We provide some lower and upper bounds for t2(G) in terms of girth, diameter or size of G. Also, for every tree T, we obtain t2(T). © 2018 World Scientific Publishing Company  

A proper vertex k-coloring of a graph G is called dynamic, if there is no vertex v∈V(G) with d(v)<2 and all of its neighbors have the same color. The smallest integer k such that G has a k-dynamic coloring is called the dynamic chromatic number of G and denoted by χ2(G). We say that v∈V(G) in a proper vertex coloring of G is a bad vertex if d(v)<2 and only one color appears in the neighbors of v. In this paper, we show that if G is a graph with the chromatic number at least 6, then there exists a proper vertex χ(G)-coloring of G such that the set of bad vertices of G is an independent set. Also, we provide some upper bounds for χ2(G)- χ(G) in terms of some parameters of the graph G  

A colorful path in a graph G is a path with χ(G) vertices whose colors are different. A v-colorful path is such a path, starting from v. Let G ≠ C7 be a connected graph with maximum degree Δ (G). We show that there exists a (Δ(G)+1)-coloring of G with a v-colorful path for every v ∈ V (G). We also prove that this result is true if one replaces (Δ (G) + 1) colors with 2 χ(G) colors. If χ (G) = ω(G), then the result still holds for χ(G) colors. For every graph G, we show that there exists a χ(G)-coloring of G with a rainbow path of length ⌊ χ(G)/2⌋ starting from each v ∈ V (G)  

In this paper we investigate two conjectures proposed in (Graphs Combin. 13 (1997) 305-314). The first one is uniquely totally colorable (UTC) conjecture which states: Empty graphs, paths, and cycles of order 3k, k a natural number, are the only UTC graphs. We show that if G is a UTC graph of order n, then Δn/2+1, where Δ is the maximum degree of G. Also there is another question about UTC graphs that appeared in (Graphs Combin. 13 (1997) 305-314) as follows: If a graph G is UTC, is it true that in the proper total coloring of G, each color is used for at least one vertex? We prove that if G is a UTC graph of order n and in the proper total coloring of G, there exists a color which did not... 

A proper vertex coloring of a graph G is called a star coloring if every two color classes induce a forest whose each component is a star, which means there is no bicolored P4 in G. In this paper, we show that the Cartesian product of any two cycles, except C3C3 and C3C5, has a 5-star coloring. © 2022 World Scientific Publishing Company  

Let G be a simple undirected uniquely vertex k-colorable graph, or a k-UCG for short. M. Truszczyński [Some results on uniquely colorable graphs, in Finite and Infinite Sets, North-Holland, Amsterdam, 1984, pp. 733--748] introduced $e^{^{*}}(G)=|V(G)|(k-1)-{k \choose 2}$ as the minimum number of edges for a k-UCG and S. J. Xu [J. Combin. Theory Ser. B, 50 (1990), pp. 319--320] conjectured that any minimal k-UCG contains a Kk as a subgraph. In this paper, first we introduce a technique called forcing. Then by applying this technique in conjunction with a feedback structure we construct a k-UCG with clique number k-t, for each $t \geq 1$ and each k, when k is large enough. This also... 

Let (Formula presented.) be a graph of order (Formula presented.) and size (Formula presented.). Suppose that (Formula presented.) is a function such that (Formula presented.). In this paper we provide a criterion for (Formula presented.)-choosability of (Formula presented.). Using this criterion, it is shown that the choice number of the complete (Formula presented.)-partite graph (Formula presented.) is (Formula presented.), which is a well-known result due to Erdös, Rubin and Taylor. Among other results we study the (Formula presented.)-choosability of the complete (Formula presented.)-partite graphs with part sizes at most (Formula presented.), when (Formula presented.), for every vertex... 

A harmonious coloring of G is a proper vertex coloring of G such that every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number of G, h(G), is the minimum number of colors needed for a harmonious coloring of G. We show that if T is a forest of order n with maximum degree Δ(T)≥n+23, then h(T) = {Δ(T)+2,if T has non-adjacent vertices of degree Δ(T);Δ(T)+1,otherwise.Moreover, the proof yields a polynomial-time algorithm for an optimal harmonious coloring of such a forest  

Color information of natural images can be considered as a highly correlated vector space. Many different color spaces have been proposed in the literature with different motivations toward modeling and analysis of this stochastic field. Recently, color transfer among different images has been under investigation. Color transferring consists of two major categories: colorizing grayscale images and recoloring colored images. The literature contains a few color transfer methods that rely on some standard color spaces. In this paper, taking advantages of the principal component analysis (PCA), we propose a unifying framework for both mentioned problems. The experimental results show the... 

Let G be a graph with n vertices and m edges and assume that f : V ( G ) → N is a function with ∑v ∈ V ( G ) f ( v ) = m + n. We show that, if we can assign to any vertex v of G a list Lv of size f ( v ) such that G has a unique vertex coloring with these lists, then G is f-choosable. This implies that, if ∑v ∈ V ( G ) f ( v ) > m + n, then there is no list assignment L such that | Lv | = f ( v ) for any v ∈ V ( G ) and G is uniquely L-colorable. Finally, we prove that if G is a connected non-regular multigraph with a list assignment L of edges such that for each edge e = u v, | Le | = max { d ( u ), d ( v ) }, then G is not uniquely L-colorable and we conjecture that this result holds for... 

Let G be a simple undirected uniquely vertex k-colorable graph, or a k-UCG for short. M. Truszczyński [Some results on uniquely colorable graphs, in Finite and Infinite Sets, North-Holland, Amsterdam, 1984, pp. 733-748] introduced e* (G) = |V(G)|(k - 1) - (k2) as the minimum number of edges for a k-UCG and S. J. Xu [J. Combin. Theory Ser. B, 50 (1990), pp. 319-320] conjectured that any minimal A-UCG contains a Kk as a subgraph. In this paper, first we introduce a technique called forcing. Then by applying this technique in conjunction with a feedback structure we construct a k-UCG with clique number k - t, for each t ≥ 1 and each k, when k is large enough. This also improves some known... 

Let G be a graph with v vertices. If there exists a collection of list of colors S1, S1,..., Sv on its vertices, each of size k, such that there exists a unique proper coloring for G from this list of colors, then G is called a uniquely k-list colorable graph. In this note we present a uniquely 3-list colorable, planar and K4-free Graph. It is a counterexample for a conjecture by Ch. Eslahchi, M. Ghebleh and H. Hajiabolhassan [3]  

In a given graph G, a set S of vertices with an assignment of colors is a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a Χ(G)-coloring of the vertices of G. A defining set with minimum cardinality is called a smallest defining set (of vertex coloring) and its cardinality, the defining number, is denoted by d(G, Χ). We study the defining number of regular graphs. Let d(n,r, Χ -k) be the smallest defining number of all r-regular k-chromatic graphs with n vertices, and f(n, k) = k-2/2(k-1)n + 2+(k-2)(k-3)/2(k-1). Mahmoodian and Mendelsohn (1999) determined the value of d(n, k, Χ = k) for all k ≤ 5, except for the case of (n, k) = (10,5).... 

A proper vertex coloring of a graph G is called a dynamic coloring if for every vertex ν with degree at least 2, the neighbors of ν receive at least two different colors. It was conjectured that if G is a regular graph, then χ2(G) - χ (G) ≤ 2. In this paper we prove that, apart from the cycles C4 and C5 and the complete bipartite graphs Kn,n, every strongly regular graph G, satisfies χ2(G) - χ (G) ≤ 1  

Let G be a graph. The core of G, denoted by GΔ, is the subgraph of G induced by the vertices of degree Δ(G), where Δ(G) denotes the maximum degree of G. A k -edge coloring of G is a function f: E(G) → L such that {pipe}L{pipe} = k and f(e1) ≠ f(e2) for all two adjacent edges e1 and e2 of G. The chromatic index of G, denoted by χ′(G), is the minimum number k for which G has a k-edge coloring. A graph G is said to be Class 1 if χ′(G) = Δ(G) and Class 2 if χ′(G) = Δ(G) + 1. In this paper it is shown that every connected graph G of even order whose core is a cycle of order at most 13 is Class 1  

Let G be a graph and for any natural number r, χs ′ (G, r) denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, χs ′ (T, 1) ≤ Δ (T) + 1. Here we generalize this result and show that χs ′ (T, 2) ≤ Δ (T) + 1. Moreover, we show that if for any two vertices u and v with maximum degree d (u, v) ≥ 3, then χs ′ (T, 2) = Δ (T). Also for any tree T with Δ (T) ≥ 3 we prove that χs ′ (T, 3) ≤ 2 Δ... 

Let G be a graph. A minimal coloring of G is a coloring which has the smallest possible sum among all proper colorings of G, using natural numbers. The vertex-strength of G, denoted by s(G), is the minimum number of colors which is necessary to obtain a minimal coloring. In this note we study these concepts, and define a new concept called the edge-strength of G, denoted by s′(G). We prove the celebrated Brooks' theorem for χ(G) replaced by s(G) and we also prove the following upper bound for s(G): s(G) ≤ ⌈col(G) + Δ(G)/2⌉, where col(G) is an invariant based on linear orderings of the vertices. Also, it is proved that s′(G) lies between Δ(G) and Δ(G) + 1, as for χ′(G), but it may be not... 

Let G be a graph and χl (G) denote the list chromatic number of G. In this paper we prove that for every graph G for which the length of each cycle is divisible by l (l ≥ 3), χl (G) ≤ 3. © 2008 Elsevier B.V. All rights reserved