Search

This paper explores a new direction in the well studied area of graph saturation—we introduce the notion of rainbow saturation. A graph G is rainbow H-saturated if there is some proper edge coloring of G which is rainbow H-free (that is, it has no copy of H whose edges are all colored distinctly), but where the addition of any edge makes such a rainbow H-free coloring impossible. Taking the maximum number of edges in a rainbow H-saturated graph recovers the rainbow Turán numbers whose systematic study was begun by Keevash, Mubayi, Sudakov, and Verstraëte. In this paper, we initiate the study of corresponding rainbow saturation number—the minimum number of edges among all rainbow H-saturated graphs. We give examples of graphs for which the rainbow saturation number is bounded away from the traditional saturation number (including all complete graphs K n for n ≥ 4 and several bipartite graphs). It is notable that there are non-bipartite graphs for which this is the case, as this does not happen when it comes to the rainbow Turán number versus the traditional Turán number. We also show that saturation numbers are at most linear for a large class of graphs, providing a partial rainbow analogue of a well known theorem of Kászonyi and Tuza. We conclude this paper with a number of related open questions and conjectures. [ABSTRACT FROM AUTHOR]

A graph H is p-edge colorable if there is a coloring ψ : E (H) → { 1 , 2 , ⋯ , p } , such that for distinct u v , v w ∈ E (H) , we have ψ (u v) ≠ ψ (v w) . The Maximum Edge-Colorable Subgraph problem takes as input a graph G and integers l and p, and the objective is to find a subgraph H of G and a p-edge-coloring of H, such that | E (H) | ≥ l . We study the above problem from the viewpoint of Parameterized Complexity. We obtain FPT algorithms when parameterized by: (1) the vertex cover number of G, by using Integer Linear Programming, and (2) l, a randomized algorithm via a reduction to Rainbow Matching, and a deterministic algorithm by using color coding, and divide and color. With respect to the parameters p + k , where k is one of the following: (1) the solution size, l, (2) the vertex cover number of G, and (3) l - mm (G) , where mm (G) is the size of a maximum matching in G; we show that the (decision version of the) problem admits a kernel with O (k · p) vertices. Furthermore, we show that there is no kernel of size O (k 1 - ϵ · f (p)) , for any ϵ > 0 and computable function f, unless NP ⊆ coNP / poly . [ABSTRACT FROM AUTHOR]

In this work, we investigate the total and edge colorings of the Kneser graphs K(n, s). We prove that the sparse case of Kneser graphs, the odd graphs O k = K (2 k - 1 , k - 1) , have total chromatic number equal to Δ (O k) + 1 . We prove that Kneser graphs K(n, 2) verify the Total Coloring Conjecture when n is even, or when n is odd not divisible by 3. For the remaining cases when n is odd and divisible by 3, we obtain a total coloring of K(n, 2) with Δ (K (n , 2)) + 3 colors when n ≡ 3 mod 4 , and with Δ (K (n , 2)) + 4 colors when n ≡ 1 mod 4 . Furthermore, we present an infinite family of Kneser graphs K(n, 2) that have chromatic index equal to Δ (K (n , 2)) . [ABSTRACT FROM AUTHOR]

For a graph G, the density of G, denoted D(G), is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class F of graphs, the value D (F) is the supremum of densities of graphs in F . A k-edge-colored graph is a finite, simple graph with edges labeled by numbers 1 , ... , k . A function from the vertex set of one k-edge-colored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class F of graphs, a k-edge-colored graph H (not necessarily with the underlying graph in F ) is k-universal for F when any k-edge-colored graph with the underlying graph in F admits a homomorphism to H . Such graphs are known to exist exactly for classes F of graphs with acyclic chromatic number bounded by a constant. The minimum number of vertices in a k-uniform graph for a class F is known to be Ω (k D (F)) and O (k D (F)) . In this paper we close the gap by improving the upper bound to O (k D (F)) for any rational D (F) . [ABSTRACT FROM AUTHOR]

We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring φ of the d-dimensional hypercube Q d , we are interested in whether there is a proper d-edge coloring of Q d that agrees with the coloring φ on every edge that is colored under φ ; or, similarly, if there is a proper d-edge coloring that disagrees with φ on every edge that is colored under φ . In particular, we prove that for any d ≥ 1 , if φ is a partial d-edge coloring of Q d , then φ is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or φ is proper and every color appears on at most d - 2 edges. We also show that φ is avoidable if d is divisible by 3 and every color class of φ is an induced matching. Moreover, for all 1 ≤ k ≤ d , we characterize for which configurations consisting of a partial coloring φ of d - k edges and a partial coloring ψ of k edges, there is an extension of φ that avoids ψ . [ABSTRACT FROM AUTHOR]

A strong edge coloring of a graph G is a proper edge coloring of G such that every color class is an induced matching. The minimum number of colors required is termed the strong chromatic index. In this paper we determine the exact value of the strong chromatic index of all unitary Cayley graphs. Our investigations reveal an underlying product structure from which the unitary Cayley graphs emerge. We then go on to give tight bounds for the strong chromatic index of the Cartesian product of two trees, including an exact formula for the product in the case of stars. Further, we give bounds for the strong chromatic index of the product of a tree with a cycle. For any tree, those bounds may differ from the actual value only by not more than a small additive constant (at most 2 for even cycles and at most 4 for odd cycles), moreover they yield the exact value when the length of the cycle is divisible by 4. [ABSTRACT FROM AUTHOR]

Large-scale sparse precision matrix estimation has attracted wide interest from the statistics community. The convex partial correlation selection method (CONCORD) developed by Khare et al. (J R Stat Soc Ser B (Stat Methodol) 77(4):803–825, 2015) has recently been credited with some theoretical properties for estimating sparse precision matrices. The CONCORD obtains its solution by a coordinate descent algorithm (CONCORD-CD) based on the convexity of the objective function. However, since a coordinate-wise update in CONCORD-CD is inherently serial, a scale-up is nontrivial. In this paper, we propose a novel parallelization of CONCORD-CD, namely, CONCORD-PCD. CONCORD-PCD partitions the off-diagonal elements into several groups and updates each group simultaneously without harming the computational convergence of CONCORD-CD. We guarantee this by employing the notion of edge coloring in graph theory. Specifically, we establish a nontrivial correspondence between scheduling the updates of the off-diagonal elements in CONCORD-CD and coloring the edges of a complete graph. It turns out that CONCORD-PCD simultanoeusly updates off-diagonal elements in which the associated edges are colorable with the same color. As a result, the number of steps required for updating off-diagonal elements reduces from p (p - 1) / 2 to p - 1 (for even p) or p (for odd p), where p denotes the number of variables. We prove that the number of such steps is irreducible In addition, CONCORD-PCD is tailored to single-instruction multiple-data (SIMD) parallelism. A numerical study shows that the SIMD-parallelized PCD algorithm implemented in graphics processing units boosts the CONCORD-CD algorithm multiple times. The method is available in the R package pcdconcord. [ABSTRACT FROM AUTHOR]

We consider, for a plane graph G and a positive integer p, an edge coloring such that the set of colors used on each face of G contains at most p colors. The maximum number of colors for such a coloring is called the facial edge-p-visibility of G. We provide several general tight lower and upper bounds for this graph coloring invariant; moreover, for certain special families of plane graphs, we determine its exact values. [ABSTRACT FROM AUTHOR]

Two distinct crossings are independent if the end-vertices of any two pairs of crossing edges are disjoint. A graph said to be plane graph with independent crossings or IC-planar, if it can be drawn in the plane such that every two crossings are independent. In this paper, we proved that every IC-planar graph G with Δ (G) = 7 admits a proper edge-coloring with Δ (G) colors if G does not contain a 6-cycle with three chords. [ABSTRACT FROM AUTHOR]

The 2-distance vertex-distinguishing index χ d 2 ′ (G) of a graph G is the minimum number of colors required for a proper edge coloring of G such that any pair of vertices at distance two have distinct sets of colors. It was conjectured that every subcubic graph G has χ d 2 ′ (G) ≤ 5 . In this paper, we confirm this conjecture for subcubic graphs with maximum average degree less than 8 3 . [ABSTRACT FROM AUTHOR]

The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy. We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su (Proc SODA 2017:2505–2523, 2017): our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2 + o (1)) Δ -edge-coloring, improving on that of Ghaffari and Su. [ABSTRACT FROM AUTHOR]

This paper addresses the edge coloring by total labeling graph problem. This is a labeling of the vertices and edges of a graph such that the weights (colors) of the edges, defined by the sum of its label and the labels of its two endpoints, determine a proper edge coloring of the graph. We propose two integer programming formulations and derive valid inequalities which are added as cutting planes on a Branch-and-Cut framework. In order to improve the efficiency of the algorithm, we also develop initial and primal heuristics. The algorithm is tested on random instances and the computational results show that it is very effective in comparison with CPLEX. It is displayed that it reduces both the CPU time (for solved instances) and the final percentage gap (for unsolved instances), and that it is capable of solving instances that are out of the reach of CPLEX. [ABSTRACT FROM AUTHOR]

It is shown that whenever the edges of a connected simple graph on n vertices are colored with n - 1 colors appearing so that no cycle in G is rainbow, there must be a monochromatic edge cut in G. From this it follows that such colorings of G can be represented, or 'encoded,' by full binary trees with n leaves, with vertices labeled by subsets of V(G), such that the leaf labels are singletons, the label of each non-leaf is the union of the labels of its children, and each label set induces a connected subgraph of G. It is also shown that n - 1 is the largest integer for which the main theorem holds, for each n, although for some graphs a certain strengthening of the hypothesis makes the theorem conclusion true with n - 1 replaced by n - 2 . [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V(G), edge set E(G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, ..., |E(G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to 1 + | E (G) | 2 ⋅ d (v) , where d(v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V(G), |{e : e ∈ Ev, f(e) ≤ Δ/2}| = |{e : e ∈ Ev, f(e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2m + 1)G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results. [ABSTRACT FROM AUTHOR]

DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced recently by Dvořák and Postle [12]. Many known upper bounds for the list-chromatic number extend to the DP-chromatic number, but not all of them do. In this note we describe some properties of DP-coloring that set it aside from list coloring. In particular, we give an example of a planar bipartite graph with DP-chromatic number 4 and prove that the edge-DP-chromatic number of a d-regular graph with d ⩾ 2 is always at least d + 1. [ABSTRACT FROM AUTHOR]

In this paper, we determine a lower bound for the multiplicity of quadrilaterals (cycles on four vertices) in complete graph Kn for any positive integer n. [ABSTRACT FROM AUTHOR]

Graph edge coloring has a rich theory, many applications and beautiful conjectures, and it is studied not only by mathematicians, but also by computer scientists. In this survey, written for the non-expert, we shall describe some main results and techniques and state some of the many popular conjectures in the theory. Besides known results a new basic result about brooms is obtained. [ABSTRACT FROM AUTHOR]

A 2-distance vertex-distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices at distance 2 have distinct sets of colors. The 2-distance vertex-distinguishing index χd2′(G) of G is the minimum number of colors needed for a 2-distance vertex-distinguishing edge coloring of G. Some network problems can be converted to the 2-distance vertex-distinguishing edge coloring of graphs. It is proved in this paper that if G is a subcubic graph, then χd2′(G)≤6. Since the Peterson graph P satisfies χd2′(P)=5, our solution is within one color from optimal. [ABSTRACT FROM AUTHOR]

Let G be a simple graph, let d(v) denote the degree of a vertex v and let g be a nonnegative integer function on V (G) with 0 ≤ g(v) ≤ d(v) for each vertex v ∈ V (G). A gc-coloring of G is an edge coloring such that for each vertex v ∈ V (G) and each color c, there are at least g(v) edges colored c incident with v. The gc-chromatic index of G, denoted by χ′gc (G), is the maximum number of colors such that a gc-coloring of G exists. Any simple graph G has the gc-chromatic index equal to δg(G) or δg(G) − 1, where δg(G)=minv∈V(G)⌊d(v)/g(v)⌋. A graph G is nearly bipartite, if G is not bipartite, but there is a vertex u ∈ V (G) such that G − u is a bipartite graph. We give some new sufficient conditions for a nearly bipartite graph G to have χ′gc (G) = δg(G). Our results generalize some previous results due to Wang et al. in 2006 and Li and Liu in 2011. [ABSTRACT FROM AUTHOR]

A graph G is of class 1 if its edges can be colored with k colors such that adjacent edges receive different colors, where k is the maximum degree of G. It is proved here that every planar graph is of class 1 if its maximum degree is at least 6 and any 6-cycle contains at most two chords. [ABSTRACT FROM AUTHOR]

The proper-trail connection number of a graph is the minimum number of colors needed to color the edges such that every pair of vertices are joined by a trail without two consecutive edges of the same color; the proper-path connection number is defined similarly. In this paper we consider these in both bridgeless graphs and graphs in general. The main result is that both parameters are tied to the maximum number of bridges incident with a vertex. In particular, we provide for k≥4 a simple characterization of graphs with proper-trail connection number k, and show that the proper-path connection number can be approximated in polynomial-time within an additive 2. [ABSTRACT FROM AUTHOR]

A maximal edge-coloring of a graph G of order n is a proper edge-coloring of G with $$\chi '(K_n)$$ colors such that no edge of the complement $$\overline{G}$$ of G can be attached to G without violating conditions of a proper edge-coloring. We almost completely determine sets of all sizes of graphs which admit maximal edge-colorings. [ABSTRACT FROM AUTHOR]

For a connected graph, we define the proper-walk connection number as the minimum number of colors needed to color the edges of a graph so that there is a walk between every pair of vertices without two consecutive edges having the same color. We show that the proper-walk connection number is at most three for all cyclic graphs, and at most two for bridgeless graphs. We also characterize the bipartite graphs that have proper-walk connection number equal to two, and show that this characterization also holds for the analogous problem where one is restricted to properly colored paths. [ABSTRACT FROM AUTHOR]

Let $$\mathcal {R}(G,H)$$ denote the set of all graphs F satisfying $$F \rightarrow (G,H)$$ and for every $$e \in E(F),$$ $$(F-e) \nrightarrow (G,H).$$ In this paper, we derive the necessary and sufficient conditions for graphs belonging to $$\mathcal {R}(mK_2,H)$$ for any graph H and each positive integer m. We give all disconnected graphs in $$\mathcal {R}(mK_2,H),$$ for any connected graph H. Furthermore, we prove that if $$F \in \mathcal {R}(mK_2,P_3),$$ then any graph obtained by subdividing one non-pendant edge in F will be in $$\mathcal {R}((m+1)K_2,P_3)$$ . [ABSTRACT FROM AUTHOR]

A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein and studied in a number of articles. Our contribution is twofold. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs. In particular, we achieve a ratio of 5/9 for subcubic bipartite graphs, improving over a 1/2-approximation algorithm proposed by Mishra. Furthermore, we study the uniquely restricted chromatic index of a graph, defined as the minimum number of uniquely restricted matchings into which its edge set can be partitioned. We provide tight upper bounds in terms of the maximum degree and characterize all extremal graphs. Our constructive proofs yield efficient algorithms to determine the corresponding edge colorings. [ABSTRACT FROM AUTHOR]

Erdős, Faber and Lovász conjectured in 1972 that the vertices of a linear hypergraph with n edges, each of size n, can be strongly colored with n colors. It was shown by Romero and Sánchez-Arroyo that an equivalent conjecture is obtained when linear hypergraphs are replaced by n-clusters. In this paper we describe new families of EFL-compliant n-clusters; that is, those for which the conjecture holds. Moreover, we describe ways to extend some n-clusters to larger ones preserving EFL-compliance. Also, our approach allowed us to provide a new upper bound for the chromatic number of n-clusters. [ABSTRACT FROM AUTHOR]

We consider a graph observability problem: how many edge colors are needed for an unlabeled graph so that an agent, walking from node to node, can uniquely determine its location from just the observed color sequence of the walk? Specifically, let G( n, d) be an edge-colored subgraph of d-dimensional (directed or undirected) lattice of size $$n^d = n \times n \times \cdots \times n$$ . We say that G( n, d) is t -observable if an agent can uniquely determine its current position in the graph from the color sequence of any t-dimensional walk, where the dimension is the number of different directions spanned by the edges of the walk. A walk in an undirected lattice G( n, d) has dimension between 1 and d, but a directed walk can have dimension between 1 and 2 d because of two different orientations for each axis. We derive bounds on the number of colors needed for t-observability. Our main result is that $$\varTheta (n^{d/t})$$ colors are both necessary and sufficient for t-observability of G( n, d), where d is considered a constant. This shows an interesting dependence of graph observability on the ratio between the dimension of the lattice and that of the walk. In particular, the number of colors for full-dimensional walks is $$\varTheta (n^{1/2})$$ in the directed case, and $$\varTheta (n)$$ in the undirected case, independent of the lattice dimension. All of our results extend easily to non-square lattices: given a lattice graph of size $$N = n_1 \times n_2 \times \cdots \times n_d$$ , the number of colors for t-observability is $$\varTheta (\root t \of {N})$$ . [ABSTRACT FROM AUTHOR]

An r-acyclic edge chromatic number of a graph G, denoted by a r( G), is the minimum number of colors used to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min {| C|, r} colors. We prove that a r( G) ≤ (4 r + 1)Δ( G), when the girth of the graph G equals to max{50, Δ( G)} and 4 ≤ r ≤ 7. If we relax the restriction of the girth to max {220, Δ( G)}, the upper bound of a r( G) is not larger than (2 r + 5)Δ( G) with 4 ≤ r ≤ 10. [ABSTRACT FROM AUTHOR]

Given a graph G, we study the problem of finding the minimum number of colors required for a proper edge coloring of G such that any pair of vertices at distance 2 have distinct sets consisting of colors of their incident edges. This minimum number is called the 2-distance vertex-distinguishing index, denoted by $$\chi '_{d2}(G)$$ . Using the breadth first search method, this paper provides a polynomial-time algorithm producing nearly-optimal solution in outerplanar graphs. More precisely, if G is an outerplanar graph with maximum degree $$\varDelta $$ , then the produced solution uses colors at most $$\varDelta +8$$ . Since $$\chi '_{d2}(G)\ge \varDelta $$ for any graph G, our solution is within eight colors from optimal. [ABSTRACT FROM AUTHOR]

The ( r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with Δ( F)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ− j and d≥2 j+2 for 0≤ j≤Δ−1. This both improves and generalizes the result for trees in Dunn, C. (Discret. Math. 307, 1767-1775, ). More broadly, we generalize the main result in Dunn, C. (Discret. Math. 307, 1767-1775, ) by showing that if G is k-degenerate with Δ( G)=Δ and j∈[Δ+ k−1], then there exists a function h( k, j) such that Alice has a winning strategy for this game with r=Δ+ k− j and d≥ h( k, j). [ABSTRACT FROM AUTHOR]

Let { G( n, l)} be the family of graphs where G( n, l) is obtained from the complete graph K by removing the edges of a complete subgraph on l vertices. In this paper, we determine the multiplicity of triangles in any two coloring of the edges of G( n, l), for sufficiently large values of n. [ABSTRACT FROM AUTHOR]

It is conjectured Zhang et al. (Appl Math Lett 15: 623-626, ) that if $$G\notin \{K_2,C_5\}$$ is a connected graph, then there is a proper edge coloring of $$G$$ using at most $$\Delta (G)+2$$ colors that distinguishes vertices of $$G$$ by means of their (naturally defined) color sets. In the paper several results concerning edge colorings of the direct product of two graphs are obtained that support the conjecture. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a graph. The core of $$G$$ , denoted by $$G_{\Delta }$$ , is the subgraph of $$G$$ induced by the vertices of degree $$\Delta (G)$$ , where $$\Delta (G)$$ denotes the maximum degree of $$G$$ . A $$k$$ -edge coloring of $$G$$ is a function $$f:E(G)\rightarrow L$$ such that $$|L| = k$$ and $$f(e_1)\ne f(e_2)$$ , for any two adjacent edges $$e_1$$ and $$e_2$$ of $$G$$ . The chromatic index of $$G$$ , denoted by $$\chi '(G)$$ , is the minimum number $$k$$ for which $$G$$ has a $$k$$ -edge coloring. A graph $$G$$ is said to be Class $$1$$ if $$\chi '(G) = \Delta (G)$$ and Class $$2$$ if $$\chi '(G) = \Delta (G) + 1$$ . Hilton and Zhao conjectured that if $$G$$ is a connected graph, $$\Delta (G_{\Delta })\le 2$$ , and $$G$$ is not the Petersen graph with one vertex removed, then $$G$$ is Class $$2$$ if and only if $$G$$ is overfull. In this paper, we prove this conjecture for claw-free graphs of even order. [ABSTRACT FROM AUTHOR]

After a necessary condition is given, 3-rainbow coloring of split graphs with time complexity O( m) is obtained by constructive method. The number of corresponding colors is at most 2 or 3 more than the minimum number of colors needed in a 3-rainbow coloring. [ABSTRACT FROM AUTHOR]

Let G be a 4-regular pseudograph. Refer as a (3, 1)- coloring of G to a coloring of its edges by several colors such that three edges of one color and one of another meet at each vertex. The properties of (3, 1)-colorings are closely connected with the presence of 3-regular subgraphs in the graph. We prove that each connected 4-regular pseudograph containing a 3-regular subgraph admits some (3, 1)-coloring. Moreover, each 4-regular pseudograph without multiple edges (but possibly with loops) has (3, 1)-coloring, which indirectly confirms the (unproven) conjecture that every such graph contains a 3-regular subgraph. We also analyze the question of the least number of colors for a (3, 1)-coloring of a given 4-regular graph. In conclusion, we prove that the existence of a (3, 1)-coloring satisfying additional requirements (an ordered (3, 1)-coloring) is equivalent to the existence of a 3-regular subgraph. [ABSTRACT FROM AUTHOR]

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 | L| = k and f ( e) ≠ f ( e) for all two adjacent edges e and e 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. [ABSTRACT FROM AUTHOR]

A multicoloring of an edge weighted graph is an assignment of intervals to its edges so that the intervals of adjacent edges do not intersect at interior points and the length of each interval is equal to the weight of the edge. The minimum length of the union of all intervals is called an edge multichromatic number of the graph. The maximum weighted degree of a vertex (i.e., the sum of the weights of all edges incident with it) is an evident lower bound of this number. There are available the examples in which the multichromatic number is one and a half times larger than the lower bound. Also, there is a conjecture that the bound cannot exceeded by a larger factor. Here we prove this conjecture for the class of unicyclic graphs. [ABSTRACT FROM AUTHOR]

For a proper edge coloring of a graph G the palette S( v) of a vertex v is the set of the colors of the incident edges. If S( u) ≠ S( v) then the two vertices u and v of G are distinguished by the coloring. A d-strong edge coloring of G is a proper edge coloring that distinguishes all pairs of vertices u and v with distance 1 ≤ d ( u, v) ≤ d. The d-strong chromatic index $${\chi_{d}^{\prime}(G)}$$ of G is the minimum number of colors of a d-strong edge coloring of G. Such colorings generalize strong edge colorings and adjacent strong edge colorings as well. We prove some general bounds for $${\chi_{d}^{\prime}(G)}$$ , determine $${\chi_{d}^{\prime}(G)}$$ completely for paths and give exact values for cycles disproving a general conjecture of Zhang et al. (Acta Math Sinica Chin Ser 49:703-708 )). [ABSTRACT FROM AUTHOR]

A k-edge-coloring f of a connected graph G is a ( λ1, λ2, ..., λβ)- defected k-edge-coloring if there is a smallest integer β with 1 ≤ β ≤ k − 1 such that the multiplicity of each color j ∈ {1, 2, ..., β} appearing at a vertex is equal to λj ≥ 2, and each color of { β + 1, β + 2, ..., k} appears at some vertices at most one time. The ( λ1, λ2, ..., λβ)- defected chromatic index of G, denoted as χ′( λ1, λ2, ..., λβ; G), is the smallest number such that every ( λ1, λ2, ..., λβ)-defected t-edge-coloring of G holds t ≥ χ′( λ1, λ2, ..., λβ; G). We obtain Δ( G) ≤ χ′( λ1, λ2, ..., λβ; G) + ( λi − 1) ≤ Δ( G) + 1, and introduce two new chromatic indices of G as: the vertex pan-biuniform chromatic indexχ′ pb( G), and the neighbour vertex pan-biuniform chromatic indexχ′ npb( G), and furthermore find the structure of a tree T having χ′ pb( T) = 1. [ABSTRACT FROM AUTHOR]

The core G of a graph G is the subgraph of G induced by the vertices of maximum degree Δ( G). In this paper, we show that if G is a connected graph with Δ( G) ≤ 2 and $${\Delta(G)\ge\frac12(|V(G)|-1)}$$, then G is of class 2 if and only if G is overfull. Our result generalizes several results of Hilton and Zhao. [ABSTRACT FROM AUTHOR]

A graph is 1-toroidal, if it can be embedded in the torus so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-toroidal graph with maximum degree Δ ≥ 10 is of class one in terms of edge coloring. Meanwhile, we show that there exist class two 1-toroidal graphs with maximum degree Δ for each Δ ≤8. [ABSTRACT FROM AUTHOR]

Semi-coloring is a new type of edge coloring of graphs. In this note, we show that every graph has a semi-coloring. This answers a problem, posed by Daniely and Linial, in affirmative. It implies that every r-regular graph has at least $${\lceil\frac{r}{2}\rceil}$$ different { K, C| i ≥ 3}-factors. [ABSTRACT FROM AUTHOR]

By an edge-coloring induced by generalization of Paley graph and computer searching, we show that that Ramsey numbers of K − e in three colors for n = 6, 7, 8, 9 are at least 472, 1102, 3208, 5962, respectively. [ABSTRACT FROM AUTHOR]

Our work is motivated by the need to manage data items on a collection of storage devices to handle dynamically changing demand. As demand for data items changes, for performance reasons, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the data migration problem. This problem was shown to be NP-hard, and an approximation algorithm achieving an approximation factor of 9.5 was presented for the half-duplex communication model in Khuller, Kim and Wan (Algorithms for data migration with cloning. SIAM J. Comput. 33(2):448-461, ). In this paper we develop an improved approximation algorithm that gives a bound of 6.5+ o(1) using new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5 using external disks. We also consider the full duplex communication model and develop an improved bound of 4+ o(1) for this model, with no external disks. [ABSTRACT FROM AUTHOR]

It is well known that if G is a multigraph then χ′( G)≥ χ′( G):=max {Δ( G),Γ( G)}, where χ′( G) is the chromatic index of G, χ′( G) is the fractional chromatic index of G, Δ( G) is the maximum degree of G, and Γ( G)=max {2| E( G[ U])|/(| U|−1): U⊆ V( G),| U|≥3, | U| is odd}. The conjecture that χ′( G)≤max {Δ( G)+1,⌈Γ( G)⌉} was made independently by Goldberg (Discret. Anal. 23:3-7, ), Anderson (Math. Scand. 40:161-175, ), and Seymour (Proc. Lond. Math. Soc. 38:423-460, ). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′( G)≤ χ′( G)+ c χ′( G) when χ′( G)> D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′( G)> ⌊(11Δ( G)+8)/10 ⌋; and Scheide recently improved this bound to χ′( G)> ⌊(15Δ( G)+12)/14 ⌋. We prove this conjecture for multigraphs G with $\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor$ , improving the above mentioned results. As a consequence, for multigraphs G with $\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}$ the answer to a 1964 problem of Vizing is in the affirmative. [ABSTRACT FROM AUTHOR]

n edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph G is denoted by $${\chi'_{vd}(G)}$$. It is proved that $${\chi'_{vd}(G)\leq\Delta(G)+5}$$ if G is a connected graph of order n ≥ 3 and $${\sigma_{2}(G)\geq\frac{2n}{3}}$$, where σ( G) denotes the minimum degree sum of two nonadjacent vertices in G. [ABSTRACT FROM AUTHOR]