Search

Tashkinov-trees have been used as a tool for proving bounds on the chromatic index, and are becoming a fundamental tool for edge-coloring. Was its publication in a language different from English an obstacle for the accessibility of a clean and complete proof of Tashkinov’s fundamental theorem? Tashkinov’s original, Russian paper offers a clear presentation of this theorem and its proof. The theorem itself has been well understood and successfully applied, but the proof is more difficult. It builds a truly amazing recursive machine, where the various cases necessitate a refined and polished analysis to fit into one another with surprising smoothness and accuracy. The difficulties were brilliantly unknotted by the author, deserving repeated attention. The present work is the result of reading, translating, reorganizing, rewriting, completing, shortcutting and annotating Tashkinov’s proof. It is essentially the same proof, with non-negligeable communicational differences though, for instance completing it wherever it occurred to be necessary, and simplifying it whenever it appeared to be possible, at the same time trying to adapt it to the habits and taste of the international graph theory community. [ABSTRACT FROM AUTHOR]

An edge-colored graph is called rainbow if every two edges receive distinct colors, and called proper if every two adjacent edges receive distinct colors. An edge-colored graph G c is properly vertex/edge-pancyclic if every vertex/edge of the graph is contained in a proper cycle of length k for every k with 3 ≤ k ≤ | V (G) | . A triangle C of G c is called a 2-triangle if C receives exactly two colors. We call G c 2-triangle-free if G c contains no 2-triangle. Let d c (v) be the number of colors on the edges incident to v in G c and let δ c (G) be the minimum d c (v) over all the vertices v ∈ V (G c) . We show in this paper that: (i) a 2-triangle-free edge-colored complete graph K n c is properly vertex-pancyclic if δ c (K n) ≥ ⌈ n 3 ⌉ + 1 , and is properly edge-pancyclic if δ c (K n) ≥ ⌈ n 3 ⌉ + 2 . (ii) with the exception of a few edge-colored graphs on at most 9 vertices, every vertex of a 2-triangle-free edge-colored complete graph K n c with δ c (K n) ≥ 4 is contained in a rainbow C 4 ; (iii) every vertex of a 2-triangle-free edge-colored complete graph K n c with δ c (K n) ≥ 5 is contained in a rainbow C 5 unless G is proper or G is a special edge-colored K 8 . [ABSTRACT FROM AUTHOR]

Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G, there exists a u-v-rainbow-cut separating them. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors that are needed in order to make G rainbow disconnected. In this paper, we first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ k ≤ n − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(G) = 3 for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph G it is NP-complete to decide whether G is rainbow disconnected.

Suppose that G is a graph and ϕ is a proper edge-coloring of G. For a vertex v ∈ V (G) , let C ϕ (v) denote the set of colors assigned to the edges incident with v. The graph G is local neighbor-distinguishing with respect to the coloring ϕ if for any two adjacent vertices x and y of degree at least two, it holds that C ϕ (x) ⊈ C ϕ (y) and C ϕ (y) ⊈ C ϕ (x) . The local neighbor-distinguishing index, denoted χ lnd ′ (G) , of G is defined as the minimum number of colors in a local neighbor-distinguishing edge-coloring of G. For n ≥ 2 , let H n denote the graph obtained from the bipartite graph K 2 , n by inserting a 2-vertex into one edge. In this paper, we show the following results: (1) For any graph G, χ lnd ′ (G) ≤ 3 Δ - 1 ; (2) suppose that G is a planar graph. Then χ lnd ′ (G) ≤ ⌈ 2.8 Δ ⌉ + 4 ; and moreover χ lnd ′ (G) ≤ 2 Δ + 10 if G contains no 4-cycles; χ lnd ′ (G) ≤ Δ + 23 if G is 3-connected; and χ lnd ′ (G) ≤ Δ + 6 if G is Hamiltonian. [ABSTRACT FROM AUTHOR]

Let G be a graph with an edge-coloring c, and let δ c (G) denote the minimum color-degree of G. A subgraph of G is called rainbow if any two edges of the subgraph have distinct colors. In this paper, we consider color-degree conditions for the existence of rainbow triangles in edge-colored graphs. At first, we give a new proof for characterizing all extremal graphs G with δ c (G) ≥ n 2 that do not contain rainbow triangles, a known result due to Li et al. Then, we characterize all complete graphs G without rainbow triangles under the condition δ c (G) = l o g 2 n , extending a result due to Li, Fujita and Zhang. Hu, Li and Yang showed that G contains two vertex-disjoint rainbow triangles if δ c (G) ≥ n + 2 2 when n ≥ 20 . We slightly refine their result by showing that the result also holds for n ≥ 6 , filling the gap of n from 6 to 20. Finally, we prove that if δ c (G) ≥ n + k 2 then every vertex of an edge-colored complete graph G is contained in at least k rainbow triangles, generalizing a result due to Fujita and Magnant. At the end, we mention some open problems. [ABSTRACT FROM AUTHOR]

An edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same. An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the graph, there exists a rainbow cut separating u and v. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors required to make G rainbow disconnected. In this paper, we first give some upper bounds for rd(G), and moreover, we completely characterize the graphs which meet the upper bounds of the Nordhaus—Gaddum type result obtained early by us. Secondly, we propose a conjecture that for any connected graph G, either rd(G) = λ+(G) or rd(G) = λ+(G)+1, where λ+(G) is the upper edge-connectivity, and prove that the conjecture holds for many classes of graphs, which supports this conjecture. Moreover, we prove that for an odd integer k, if G is a k-edge-connected k-regular graph, then χ′(G) = k if and only if rd(G) = k. It implies that there are infinitely many k-edge-connected k-regular graphs G for which rd(G)= λ+(G)for odd k, and also there are infinitely many k-edge-connected k-regular graphs G for which rd(G)= λ+(G) + 1 for odd k. For k = 3, the result gives rise to an interesting result, which is equivalent to the famous Four-Color Problem. Finally, we give the relationship between rd(G) of a graph G and the rainbow vertex-disconnection number rvd(L(G)) of the line graph L(G) of G. [ABSTRACT FROM AUTHOR]

For an edge-colored graph G, a set F of edges of G is called a proper edge-cut if F is an edge-cut of G and any pair of adjacent edges in F are assigned different colors. An edge-colored graph is proper disconnected if for each pair of distinct vertices of G there exists a proper edge-cut separating them. For a connected graph G, the proper disconnection number of G, denoted by pd(G), is the minimum number of colors that are needed in order to make G proper disconnected. In this paper, we first give the exact values of the proper disconnection numbers for some special families of graphs. Next, we obtain a sharp upper bound of pd(G) for a connected graph G of order n, i.e, p d (G) ≤ min { χ ′ (G) - 1 , n 2 } . Finally, we show that for given integers k and n, the minimum size of a connected graph G of order n with p d (G) = k is n - 1 for k = 1 and n + 2 k - 4 for 2 ≤ k ≤ ⌈ n 2 ⌉ . [ABSTRACT FROM AUTHOR]

For an r-regular graph G, we define an edge-coloring c with colors from {1, 2, . . . , k}, in such a way that any vertex of G is incident with at least one edge of each color. The multiset-color cm(v) of a vertex v is defined as the ordered tuple (a1, a2, . . . , ak), where ai (1 ≤ i ≤ k) denotes the number of edges of color i which are incident with v in G. Then this edge-coloring c is called a k-kaleidoscopic coloring of G if every two distinct vertices in G have different multiset-colors and in this way the graph G is defined as a k-kaleidoscope. In this paper, we determine the integer k for a complete graph Kn to be a k-kaleidoscope, and hence solve a conjecture in [P. Zhang, A Kaleidoscopic View of Graph Colorings, (Springer Briefs in Math., New York, 2016)] that for any integers n and k with n ≥ k + 3 ≥ 6, the complete graph Kn is a k-kaleidoscope. Then, we construct an r-regular 3-kaleidoscope of order ( 2r-1)-1$\left( {_{\,\,\,2}^{r - 1}} \right) - 1$ − 1 for each integer r ≥ 7, where r ≡ 3 (mod 4), which solves another conjecture in [P. Zhang, A Kaleidoscopic View of Graph Colorings, (Springer Briefs in Math., New York, 2016)] on the maximum order of r-regular 3-kaleidoscopes.

Let G be a plane graph. Two edges are facially adjacent in G if they are consecutive edges on the boundary walk of a face of G. Given nonnegative integers r, s, and t, a facial [r, s, t]-coloring of a plane graph G = (V,E) is a mapping f : V ∪ E → {1, . . ., k} such that |f(v1) − f(v2)| ≥ r for every two adjacent vertices v1 and v2, |f(e1) − f(e2)| ≥ s for every two facially adjacent edges e1 and e2, and |f(v) − f(e)| ≥ t for all pairs of incident vertices v and edges e. The facial [r, s, t]-chromatic number ̄ χr,s,t(G) of G is defined to be the minimum k such that G admits a facial [r, s, t]-coloring with colors 1, . . ., k. In this paper we show that ̄ χr,s,t(G) ≤ 3r + 3s + t + 1 for every plane graph G. For some triplets [r, s, t] and for some families of plane graphs this bound is improved. Special attention is devoted to the cases when the parameters r, s, and t are small.

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. The conflict-free connection number of a connected graph G, denoted by cfc(G), is defined as the minimum number of colors that are required in order to make G conflict-free connected. In this paper, we investigate the relation between the conflict-free connection number and the independence number of a graph. We firstly show that cfc(G) ≤ α(G) for any connected graph G, and give an example to show that the bound is sharp. With this result, we prove that if T is a tree with Δ (T) ≥ α (T) + 2 2 , then cfc(T) = Δ(T). [ABSTRACT FROM AUTHOR]

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. In this paper the question for the smallest number of colors needed for a coloring of edges of G in order to make it conflict-free connected is investigated. We show that the answer is easy for 2-edge-connected graphs and very difficult for other connected graphs, including trees.

The proper connection number of a graph G, denoted by pc(G), is the minimum number of colors needed to color the edges of G so that every pair of distinct vertices of G is connected by a path in which no two adjacent edges of the path receive the same color. A connected graph G is k-PC if pc(G) ≤ k. In the literature, it is shown that every 3-edge-connected graph is 2-PC and every 2-edge-connected graph is 3-PC. We show in this paper that every 2-connected graph such that each edge is contained in a cycle of length at most 4 is 2-PC, and every 2-connected graph with minimum degree at least 3 such that each edge is contained in a cycle of length at most 6 is 2-PC. [ABSTRACT FROM AUTHOR]

A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer k for which there exists a k-edge-coloring of G such that every pair of distinct vertices of G is connected by a rainbow path. Let f(d) denote the minimum number such that rc(G) ≤ f(d) for each bridgeless graph G with diameter d. In this paper, we shall show that 7 ≤ f(3) ≤ 9.

An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index χr′(G)$\chi _r^\prime (G)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that χr′(G)≤3$\chi _r^\prime (G) \le 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with χ1′(G)=i$\chi _1^\prime (G) = i$ , i = 1, 2, 3 are characterized. The precise value of the r-maximum index, r ≥ 1, is determined for trees and complete graphs.

An edge-colored graph G is conflict-free connected if every two of its vertices are connected by a path, which contains a color used on exactly one of its edges. The conflict-free connection number of a connected graph G, denoted by cfc(G), is the smallest number of colors needed in order to make G conflict-free connected. For a graph G,  let C(G) be the subgraph of G induced by its set of cut-edges. In this paper, we first show that, if G is a connected non-complete graph G of order n≥9 with C(G) being a linear forest and with the minimum degree δ(G)≥max{3,n-45}, then cfc(G)=2. The bound on the minimum degree is best possible. Next, we prove that, if G is a connected non-complete graph of order n≥33 with C(G) being a linear forest and with d(x)+d(y)≥2n-95 for each pair of two nonadjacent vertices x, y of V(G), then cfc(G)=2. Both bounds, on the order n and the degree sum, are tight. Moreover, we prove several results concerning relations between degree conditions on G and the number of cut edges in G. [ABSTRACT FROM AUTHOR]

A path P in an edge-colored graph G is called a proper path if no two adjacent edges of P are colored the same, and G is proper connected if every two vertices of G are connected by a proper path in G. The proper connection number of a connected graph G, denoted by pc(G), is the minimum number of colors that are needed to make G proper connected. In this paper, we study the proper connection number on the lexicographic, strong, Cartesian, and direct products and present exact values or upper bounds for these products of graphs. [ABSTRACT FROM AUTHOR]

A tree T in an edge-colored graph is a proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be a fixed integer with 2≤k≤n. For a vertex subset S⊆V(G) with S≥2, a tree containing all the vertices of S in G is called an S-tree. An edge-coloring of G is called a k-proper coloring if for every k-subset S of V(G), there exists a proper S-tree in G. For a connected graph G, the k-proper index of G, denoted by pxk(G), is the smallest number of colors that are needed in a k-proper coloring of G. In this paper, we show that for every connected graph G of order n and minimum degree δ≥3, px3(G)≤nln(δ+1)δ+1(1+oδ(1))+2. We also prove that for every connected graph G with minimum degree at least 3, px3(G)≤px3(G[D])+3 when D is a connected 3-way dominating set of G and px3(G)≤px3(G[D])+1 when D is a connected 3-dominating set of G. In addition, we obtain sharp upper bounds of the 3-proper index for two special graph classes: threshold graphs and chain graphs. Finally, we prove that px3(G)≤⌊n2⌋ for any 2-connected graph with at least four vertices. [ABSTRACT FROM AUTHOR]

Every critical graph is connected on proper edge-colorings of simple graphs. In contrast, there not only exist connected critical graphs but exist disconnected critical graphs on $$g_c$$ -colorings of simple graphs. In this article, disconnected $$g_c$$ -critical graphs are studied firstly and their structure characteristics are depicted. [ABSTRACT FROM AUTHOR]

In this paper we study alternating cycles in graphs embedded in a surface. We observe that 4-vertex-colorability of a triangulation on a surface can be expressed in terms of spanninq quadrangulations, and we establish connections between spanning quadrangulations and cycles in the dual graph which are noncontractible and alternating with respect to a perfect matching. We show that the dual graph of an Eulerian triangulation of an orientable surface other than the sphere has a perfect matching M and an M-alternating noncontractible cycle. As a consequence, every Eulerian triangulation of the torus has a nonbipartite spanning quadrangulation. For an Eulerian triangulation G of the projective plane the situation is different: If the dual graph $$G^*$$ is nonbipartite, then $$G^*$$ has no noncontractible alternating cycle, and all spanning quadrangulations of G are bipartite. If the dual graph $$G^*$$ is bipartite, then it has a noncontractible, M-alternating cycle for some (and hence any) perfect matching, G has a bipartite spanning quadrangulation and also a nonbipartite spanning quadrangulation. [ABSTRACT FROM AUTHOR]

Cockayne and Lorimer proved that in any 2-edge-coloring of $$K_{2s+t-1}$$ $$(s\ge t\ge 1)$$ there exists an s-matching receiving the same color (we call such matching monochromatic matching) or a t-matching having another color. In this paper, we show that the number of such monochromatic matchings may be exponentially many. We prove that in any 2-edge-coloring of $$K_{2s+t-1} (s \ge t \ge 1)$$ there are either at least $$2^{[t/2]}f(n)$$ many monochromatic s-matchings or at least $$2^{[t/2]}$$ many t-matchings of another color, where $$f(n)=(2n+1)!!$$ , and $$n=s-t$$ . These generalize a Ramsey number by Erdös, Gyárfás and Pyber, Gerencsér and Gyárfás and improve a lower bound of the number of such matching by Cao and Ren as well. [ABSTRACT FROM AUTHOR]

An edge colored graph is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number, rc-number for short, of a graph $${\varGamma }$$ , is the smallest number of colors that are needed in order to make $${\varGamma }$$ rainbow connected. In this paper, we give a method to bound the rc-numbers of graphs with certain structural properties. Using this method, we investigate the rc-numbers of Cayley graphs, especially, those defined on abelian groups and on dihedral groups. [ABSTRACT FROM AUTHOR]

An edge-coloring of a graph G is an assignment of colors to all the edges of G. A g -coloring of a graph G is an edge-coloring of G such that each color appears at each vertex at least g( v) times. The maximum integer k such that G has a g -coloring with k colors is called the g -chromatic index of G and denoted by $$\chi\prime_{g_{c}}$$ ( G). In this paper, we extend a result on edge-covering coloring of Zhang and Liu in 2011, and give a new sufficient condition for a simple graph G to satisfy $$\chi\prime_{g_{c}}$$ ( G) = δ ( G), where $$\delta_{g}\left(G\right) = min_{v\epsilon V (G)}\left\{\lfloor\frac{d\left(v\right)}{g\left(v\right)}\rfloor\right\}$$ . [ABSTRACT FROM AUTHOR]

An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG( v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with , i = 1, 2, 3 are characterized. The precise value of the r-maximum index, r ≥ 1, is determined for trees and complete graphs. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is rainbow connected if every pair of vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number rc( G) of G is defined to be the minimum integer t such that there exists an edge-coloring of G with t colors that makes G rainbow connected. For a graph G without any cut vertex, i.e., a 2-connected graph, of order n, it was proved that $${rc(G)\leq\lceil\frac{n}{2} \rceil}$$ and the bound is tight. In this paper, we prove that for a connected graph G of order n with at least one cut vertex, $${rc(G) \leq\frac{n+r-1} 2}$$ , where r is the number of blocks of G with even orders, and the upper bound is tight. Moreover, we also obtain a tight upper bound $${\lfloor(2n-2)/3\rfloor}$$ for the rainbow connection number of a bridgeless (2-edge-connected) graph of order n. [ABSTRACT FROM AUTHOR]

The automorphic H-chromatic index of a graph Γ is the minimum integer m for which Γ has a proper edge-coloring with m colors preserved by a given subgroup H of the full automorphism group of Γ. We determine upper bounds for this index in terms of the chromatic index of Γ for some abelian 2-groups H. [ABSTRACT FROM AUTHOR]

An edge-colored graph G, where adjacent edges may have the same color, is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. A graph G is d-rainbow connected if one can use d colors to make G rainbow connected. For integers n and d let t( n, d) denote the minimum size (number of edges) in d-rainbow connected graphs of order n. Schiermeyer got some exact values and upper bounds for t( n, d). However, he did not present a lower bound of t( n, d) for $${3 \leq d < \lceil\frac{n}{2}\rceil}$$ . In this paper, we improve his lower bound of t( n, 2), and get a lower bound of t( n, d) for $${3 \leq d < \lceil\frac{n}{2}\rceil}$$ . [ABSTRACT FROM AUTHOR]