Search

We study an edge coloring problem in multigraphs, in which each node incurs a cost equal to the number of appearances of the most frequent color among those received by its incident edges. We seek an edge coloring with a given number w of colors, that minimizes the total cost incurred by the nodes of the multigraph. We consider a class of approximation algorithms for this problem, which are based on orienting the edges of the multigraph, then grouping appropriately the incoming and outgoing edges at each node so as to construct a bipartite multigraph of maximum degree w , and finally obtaining a proper edge coloring of this bipartite multigraph. As shown by Nomikos et al. (2001), simply choosing an arbitrary edge orientation in the first step yields a 2-approximation algorithm. We investigate whether this approximation ratio can be improved by a more careful choice of the edge orientation in the first step. We prove that, assuming a worst-case bipartite edge coloring, this is not possible in the asymptotic sense, as there exists a family of instances in which any orientation gives a solution with cost at least 2 − Θ ( 1 w ) times the optimal. On the positive side, we show how to produce an orientation which results in a solution with cost within a factor of 2 − 1 2 w of the optimal, thus yielding an approximation ratio strictly better than 2. This improvement is important in view of the fact that this graph-theoretic problem models, among others, wavelength assignment to communication requests in multifiber optical star networks. In this context, the parameter w corresponds to the number of available wavelengths per fiber, which is limited in practice due to technological constraints. [ABSTRACT FROM AUTHOR]

A graph is said to be of class 1 if its edge chromatic number is equal to the maximum degree of this graph. Let G be a planar graph with maximum degree Δ ≥ 6 and without adjacent 7-cycles, then G is of class 1. [ABSTRACT FROM AUTHOR]

This paper explores the scheduling problem of input-queued switches, based on a new algebraic method of edge coloring called complex coloring. The proposed scheduling algorithm possesses three important features inherent from complex coloring: parallelizability, optimality and rearrangeability. Parallelizability makes the algorithm running very fast in a distributed manner, optimality ensures that the algorithm always returns a proper connection pattern with the minimum number of required colors, and rearrangeability allows partially re-scheduling the existing connection patterns if the traffic patterns only changes slightly. The amortized time complexity of the proposed parallel scheduling algorithm, in terms of the time to compute a matching in a timeslot, is [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]

V.G. Vizing showed that any graph belongs to one of two classes: Class 1 if γ(G) = Δ(G) or in class 2 if γ(G) = Δ(G) + 1, where γ(G) and Δ(G) denote the edge chromatic index of G and the maximum degree of G, respectively. This paper addresses the problem of finding the edge chromatic surplus of a cubic graph G in Class 2, namely the minimum cardinality of colour classes over all 4-edge chromatic colourings of E(G). An approach to face this problem - using a new parameter q - is given in [1]. Computing q is difficult for the general case of graph G, so there is the need to find restricted classes of G, where q is easy to compute. Working in the same sense as in this paper we give an upper bound of the edge chromatic surplus for a special type of cubic graphs, that is the class of bridgeless non-planar cubic graphs in which in each pair of crossing edges, the crossing edges are adjacent to a third edge. [ABSTRACT FROM AUTHOR]

To carry out a clique search in a given graph in a parallel fashion, one divides the problem into a very large number of smaller instances. To sort out as many resulted smaller problems as possible, one can rely on upper estimates of the clique sizes. Legal coloring of the nodes of the graphs is a commonly used tool to establish upper bound of the clique size. We will point out that coloring of the nodes can also be used to divide the clique search problem into smaller ones. We will introduce a non-conventional coloring of the edges of the given graph. We will gather theoretical and computational evidence that the proposed edge coloring provides better estimates for the clique size than the node coloring and can be used to divide the original problem into subproblems. [ABSTRACT FROM AUTHOR]

Given t distinct colors, we order the t subsets of t - 1 colors in some arbitrary manner. Let G1, G2, . . ., Gt be graphs. The (t - 1)-chromatic Ramsey number, denoted by γt t-1(G1, G2, . . ., Gt), is defined to be the least number n such that if the edges of the complete graph Kn are colored in any fashion with t colors, then for some i the subgraph whose edges are colored with the ith subset of colors contains a Gi. In this paper, we find the value of γ5 4(G1, . . ., G5) when each Gi is a path. [ABSTRACT FROM AUTHOR]

We call an edge-coloring of a graph G a rainbow coloring if the edges of G are colored with distinct colors. For every even positive integer k≥4, let f(n,k) denote the minimum number of colors required to color the edges of the n-dimensional cube Qn, so that every copy of Ck is rainbow. Faudree et al. [6] proved that f(n,4)=n for n=4 or n>5. Mubayi et al. [8] showed that n≤f(n,6)

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]

We show that the inequality H(A | B,X) + H(A | B,Y) \leqslant H(A | B) for jointly distributed random variables A,B,X,Y , which does not hold in general case, holds under some natural condition on the support of the probability distribution of A,B,X,Y . This result generalizes a version of the conditional Ingleton inequality: if for some distribution , then I(A \mskip 5mu {:} \mskip 5mu B) \leqslant I(A \mskip 5mu {:} \mskip 5mu B | X) + I(A \mskip 5mu {:} \mskip 5mu B | Y) + I(X \mskip 5mu {:} \mskip 5mu Y) . We present two applications of our result. The first one is the following easy-to-formulate theorem on edge colorings of bipartite graphs: assume that the edges of a bipartite graph are colored in K$ colors so that each two edges sharing a vertex have different colors and for each pair (left vertex $x$ , right vertex $y$ ) there is at most one color $a$ such both $x$ and $y$ are incident to edges with color $a$ ; assume further that the degree of each left vertex is at least $L$ and the degree of each right vertex is at least $R$ . Then $K \geqslant LR$ . The second application is a new method to prove lower bounds for biclique cover of bipartite graphs. [ABSTRACT FROM PUBLISHER]

A matching M in a graph G is r -degenerate if the subgraph of G induced by the set of vertices incident with an edge in M is r -degenerate. Goddard, Hedetniemi, Hedetniemi, and Laskar (Generalized subgraph-restricted matchings in graphs, Discrete Mathematics 293 (2005) 129–138)introduced the notion of acyclic matchings, which coincide with 1-degenerate matchings. Solving a problem they posed, we describe an efficient algorithm to determine the maximum size of an r -degenerate matching in a given chordal graph. Furthermore, we study the r -chromatic index of a graph defined as the minimum number of r -degenerate matchings into which its edge set can be partitioned, obtaining upper bounds and discussing extremal graphs. [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]

An interval t -coloring of a multigraph G is a proper edge coloring with colors 1 , … , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors. A cyclic interval t -coloring of a multigraph G is a proper edge coloring with colors 1 , … , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t . Denote by w ( G ) ( w c ( G ) ) and W ( G ) ( W c ( G ) ) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph G , respectively. We present some new sharp bounds on w ( G ) and W ( G ) for multigraphs G satisfying various conditions. In particular, we show that if G is a 2 -connected multigraph with an interval coloring, then W ( G ) ≤ 1 + | V ( G ) | 2 ( Δ ( G ) − 1 ) . We also give several results towards the general conjecture that W c ( G ) ≤ | V ( G ) | for any triangle-free graph G with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most 4 . [ABSTRACT FROM AUTHOR]

The least k such that a given digraph D = ( V , A ) can be arc-labeled with integers in the interval [ 1 , k ] so that the sum of values in-coming to x is distinct from the sum of values out-going from y for every arc ( x , y ) ∈ A , is denoted by χ ̄ Ł e ( D ) . This corresponds to one of possible directed versions of the well-known 1-2-3 Conjecture. Unlike in the case of other possibilities, we show that χ ̄ Ł e ( D ) is unbounded in the family of digraphs for which this parameter is well defined. However, if the family is restricted by excluding the digraphs with so-called lonely arcs, we prove that χ ̄ Ł e ( D ) ≤ 4 , and we conjecture that χ ̄ Ł e ( D ) ≤ 3 should hold. [ABSTRACT FROM AUTHOR]

A proper edge coloring of a graph G with colors [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]

An experimental design is studied where mice should be placed into cages according to two different constraint settings. In the first one, mice are placed in contiguous cages with the constraint of changing cage at each day t, avoiding neighbours of days t - 1 and t + 1 and meeting in the end all other mice. In the second setting, an additional constraint compels mice to change side at each step so that one half of the mice meets only the other half. A method is presented for the first setting and two for the second one, one of the latter taking advantage of finite fields in a simple and very similar way to what happens when dealing with mutually orthogonal latin squares. [ABSTRACT FROM AUTHOR]

Vizing conjectured that every edge chromatic critical graph contains a 2-factor. Believing that stronger properties hold for this class of graphs, Luo and Zhao (2013) showed that every edge chromatic critical graph of order n with maximum degree at least 6 n 7 is Hamiltonian. Furthermore, Luo et al. (2016) proved that every edge chromatic critical graph of order n with maximum degree at least 4 n 5 is Hamiltonian. In this paper, we prove that every edge chromatic critical graph of order n with maximum degree at least 3 n 4 is Hamiltonian. Our approach is inspired by the recent development of Kierstead path and Tashkinov tree techniques for multigraphs. [ABSTRACT FROM AUTHOR]

A well-known theorem due to Vizing states that every graph with maximum degree Δ is Δ- or (Δ + 1) -edge-colorable. Recently, Behr extended the concept of edge coloring in a natural way to signed graphs. He also proved that an analogue of Vizing's Theorem holds for all signed graphs. Adopting Behr's definition, Zhang et al. proved that a signed planar graph G with maximum degree Δ is Δ-edge-colorable if either Δ ≥ 10 or Δ ∈ { 8 , 9 } and G contains no adjacent triangles. They also proposed the conjecture that every signed planar graph with Δ ≥ 6 is Δ-edge-colorable, as a generalization of Vizing's Planar Graph Conjecture. In this paper, we prove that every signed planar graph with Δ ≥ 8 is Δ-edge-colorable. [ABSTRACT FROM AUTHOR]

It is well known that if the edges of a finite simple connected graph on n vertices are colored so that no cycle is rainbow, then no more than n-1 colors can appear on the edges. In previous work it has been shown that the essentially different rainbow-cycle-forbidding edge colorings of Kn with n-1 colors appearing are in 1-1 correspondence with (can be encoded by) the (isomorphism classes of) full binary trees with n leafs. In the encoding, the natural Huffman labeling of each tree arising from the assignment of 1 to each leaf plays a role. Very recently it has been shown that a similar encoding holds for rainbow-cycle-forbidding edge colorings of Ka,b with a+b-1 colors appearing. In this case the binary trees are given Huffman labelings arising from certain assignments of (0,1) or (1,0) to the leafs. (Sibling leafs are not allowed to be assigned the same label.) In this paper we prove the analogous result for complete r-partite graphs, for r > 2.

Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.

A twin edge k-coloring of a graph G is a proper edge coloring of G with the elements of Zk so that the induced vertex coloring in which the color of a vertex v in G is the sum (in Zk) of the colors of the edges incident with v is a proper vertex coloring. The minimum k for which G has a twin edge k-coloring is called the twin chromatic index of G. Among the results presented are formulas for the twin chromatic index of each complete graph and each complete bipartite graph

In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤. It is known that α (G) < |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤|V | when △ ≥ 5 and n2 ≤ 2(△− 1)

An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed trees