Search

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]

Let g(t) be the minimum number such that every graph G with average degree d(G) ≥ g(t)containsa Kt-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that g(t) ∈ Θ(t √log t). This paper shows that for all fixed ε > 0 and fixed sufficiently large t ≥ t(ε), if d(G) ≥ (2 + ε)g(t), then we can find this Kt-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when d(G) ≥ 2t-2. [ABSTRACT FROM AUTHOR]

For a graph G and for each vertex v ∈ V (G), let Λ[sub G](v)= {EG(v, 1),E[sub G](v, 2),..., E[sub G](v, κ[sub v])} be a partition of the edges incident with v. Let ΛG = {ΛG(v) | v ∈ V (G)}. We call the pair (G, ΛG) a partitioned graph. Let κ = maxv κv and let g, f : V (G) x {1,..., κ} → ℕ and t, u : V (G) → ℕ be functions where, for all vertices v ∈ V (G), (i) g(v, i) ≤ f(v, i) ≤ dG(v, i) i = 1,..., κv, (ii) ... and ... . A subgraph H of the partitioned graph is said to be a (g, f, u, t)-factor if all vertices v ∈ V (G) satisfy(a) g(v, i) ≤ dH(v, i) ≤ f(v, i),i =1,..., κv and (b) u(v) ≤ dH (v) ≤ t(v), where dH(v, i)= |E(H) ∩ EG(v, i)|. In this paper, we shall show via a reduction to a matching problem, that there is a good algorithm for determining whether a partitioned graph has a (g, f, u, t)-factor. Second, we shall also prove a theorem which characterizes the existence of (0, f, t, u)-factors in a partitioned graph when u(v)