Search

Let be a graph with a positive integer weight for each vertex . One wishes to assign each edge of a positive integer as a color so that for any vertex and any two edges and incident to . Such an assignment is called an -edge-coloring of , and the maximum integer assigned to edges is called the span of . The -chromatic index of is the minimum span over all -edge-colorings of . In the paper, we present various upper and lower bounds on the -chromatic index, and obtain three efficient algorithms to find an -edge-coloring of a given graph. One of them finds an -edge-coloring with span smaller than twice the -chromatic index. [ABSTRACT FROM AUTHOR]

Given a multigraph G=(V, E) with a positive rational weight w(e) on each edge e, the weighted density problem (WDP) is to find a subset $U$ of V, with |U| ≥ 3 and odd, that maximizes 2w(U)/(|U|-1), where w(U) is the total weight of all edges with both ends in U, and the weighted fractional edge-coloring problem can be formulated as the following linear program: minimize 1Tx subject to Ax = w, x ≥ 0, where $A$ is the edge-matching incidence matrix of $G$. These two problems are closely related to the celebrated Goldberg-Seymour conjecture on edge-colorings of multigraphs, and are interesting in their own right. Even when w(e) = 1 for all edges e, determining whether WDP can be solved in polynomial time was posed by Jensen and Toft [Topics in Chromatic Graph Theory, Cambridge University Press, Cambridge, 2015, pp. 327-357] and by Stiebitz et al. [Graph Edge Colouring: Vizing's Theorem and Goldberg's Conjecture, John Wiley, New York, 2012] as an open problem. In this paper we present strongly polynomial-time algorithms for solving them exactly, and develop a novel matching removal technique for multigraph edge-coloring. [ABSTRACT FROM AUTHOR]