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]

In this paper, we show the Erdős-Pósa property for edge-disjoint packing of S-closed walks with parity constraints in 4-edge-connected graphs. More precisely, we prove that for any 4-edge-connected graph G and any vertex subset S, either G h as k edge-disjoint elementary closed odd walks, each of which has at least one vertex of S, or G has an edge set F with |F| < f (k) such that G - F has no such walks. The 4-edge-connectivity is the best possible in the sense that 3-edge-connected graphs do not satisfy the statement. Since the proof is constructive, we can design a fixed-parameter algorithm for finding k edge-disjoint walks satisfying the conditions in a 4-edge-connected graph for a parameter k. In addition, this gives a simple fixed-parameter algorithm for the parity edge-disjoint walks problem with k terminal pairs. [ABSTRACT FROM AUTHOR]

A total-weighting of a graph G = (V, E) is a mapping f which assigns to each element y ∈ V ∪ E a real number f (y) as the weight of y. A total-weighting f of G is proper if the coloring øf of the vertices of G defined as øf (v) = f (v) + Σe∈E(v) f (e) is a proper coloring of G, i.e., øf of (v) ≠ øf of (u) for any edge uv, where E(v) is the set of edges of G incident to v. For positive integers k and k', a graph G is called (k, k')-total-weight-choosable if whenever each vertex v is given k permissible weights and each edge e is given k' permissible weights, there is a proper total-weighting f of G which uses only permissible weights on each element y ∈ V ∪ E. It is known that every tree is (2, 2)-total-weight-choosable and every tree other than K2 is (1, 3)-total-weight-choosable. However, the problem of determining which trees are (1, 2)-total-weight-choosable remained open. This paper solves this problem and characterizes all (1, 2)-total-weight-choosable trees. Based on this characterization, we give an algorithm that determines in linear time whether a given tree is (1, 2)-total-weight-choosable. [ABSTRACT FROM AUTHOR]

Let G be an interval graph and take one of its vertices x. Can we find in linear time a minimum number of vertex disjoint paths of G which cover the vertex set of G and have x as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches. [ABSTRACT FROM AUTHOR]

In the PROPER INTERVAL COMPLETION problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of PROPER INTERVAL COMPLETION from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir, and Tarjan [SIAM J. Comput., 28 (1999), pp. 1906-1922], who showed an algorithm for the problem working in O(16k (n+m)) time. In this paper we present an algorithm with running time kO(k2/3) + O(nm(kn + m)), which is the first subexponential parameterized algorithm for PROPER INTERVAL COMPLETION. [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)