An official website of the United States government
Abstract Given a multigraph$$G=(V,E)$$, the edge-coloring problem (ECP) is to color the edges ofGwith the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer program, and its linear programming relaxation is referred to as the fractional edge-coloring problem (FECP). The optimal value of ECP (resp. FECP) is called the chromatic index (resp. fractional chromatic index) ofG, denoted by$$\chi '(G)$$(resp.$$\chi ^*(G)$$). Let$$\Delta (G)$$be the maximum degree ofGand let$$\Gamma (G)$$be the density ofG, defined by$$\begin{aligned} \Gamma (G)=\max \left\{ \frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hspace{5.69054pt}\textrm{and} \hspace{5.69054pt}\textrm{odd} \right\} , \end{aligned}$$whereE(U) is the set of all edges ofGwith both ends inU. Clearly,$$\max \{\Delta (G), \, \lceil \Gamma (G) \rceil \}$$is a lower bound for$$\chi '(G)$$. As shown by Seymour,$$\chi ^*(G)=\max \{\Delta (G), \, \Gamma (G)\}$$. In the early 1970s Goldberg and Seymour independently conjectured that$$\chi '(G) \le \max \{\Delta (G)+1, \, \lceil \Gamma (G) \rceil \}$$. Over the past five decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated an important body of work. In this paper we present a proof of this conjecture. Our result implies that, first, there are only two possible values for$$\chi '(G)$$, so an analogue to Vizing’s theorem on edge-colorings of simple graphs holds for multigraphs; second, although it isNP-hard in general to determine$$\chi '(G)$$, we can approximate it within one of its true value, and find it exactly in polynomial time when$$\Gamma (G)>\Delta (G)$$; third, every multigraphGsatisfies$$\chi '(G)-\chi ^*(G) \le 1$$, and thus FECP has a fascinating integer rounding property.
more »
« less
Local version of Vizing's theorem for multigraphs
Abstract Extending a result of Christiansen, we prove that every multigraph admits a proper edge colouring which islocal, that is, for every edge with end‐points , where (resp. ) denotes the degree of a vertex (resp. the maximum edge multiplicity at ). This is derived from a local version of the Fan Equation.
more »
« less
- Award ID(s):
- 2154160
- PAR ID:
- 10528015
- Publisher / Repository:
- Wiley Periodicals, LLC
- Date Published:
- Journal Name:
- Journal of Graph Theory
- ISSN:
- 0364-9024
- Subject(s) / Keyword(s):
- edge colouring local colouring multigraphs Vizing's theorem
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
An edge‐ordered graph is a graph with a linear ordering of its edges. Two edge‐ordered graphs areequivalentif there is an isomorphism between them preserving the edge‐ordering. Theedge‐ordered Ramsey number redge(H; q) of an edge‐ordered graphHis the smallestNsuch that there exists an edge‐ordered graphGonNvertices such that, for everyq‐coloring of the edges ofG, there is a monochromatic subgraph ofGequivalent toH. Recently, Balko and Vizer proved thatredge(H; q) exists, but their proof gave enormous upper bounds on these numbers. We give a new proof with a much better bound, showing there exists a constantcsuch thatfor every edge‐ordered graphHonnvertices. We also prove a polynomial bound for the edge‐ordered Ramsey number of graphs of bounded degeneracy. Finally, we prove a strengthening for graphs where every edge has a label and the labels do not necessarily have an ordering.more » « less
-
Abstract Checking satisfiability of formulae in the theory of linear arithmetic has far reaching applications, including program verification and synthesis. Many satisfiability solvers excel at proving and disproving satisfiability of quantifier-free linear arithmetic formulas and have recently begun to support quantified formulas. Beyond simply checking satisfiability of formulas, fine-grained strategies for satisfiability games enables solving additional program verification and synthesis tasks. Quantified satisfiability games are played between two players—SAT and UNSAT—who take turns instantiating quantifiers and choosing branches of boolean connectives to evaluate the given formula. A winning strategy for SAT (resp. UNSAT) determines the choices of SAT (resp. UNSAT) as a function of UNSAT ’s (resp. SAT ’s) choices such that the given formula evaluates to true (resp. false) no matter what choices UNSAT (resp. SAT) may make. As we are interested in both checking satisfiabilityandsynthesizing winning strategies, we must avoid conversion to normal-forms that alter the game semantics of the formula (e.g. prenex normal form). We present fine-grained strategy improvement and strategy synthesis, the first technique capable of synthesizing winning fine-grained strategies for linear arithmetic satisfiability games, which may be used in higher-level applications. We experimentally evaluate our technique and find it performs favorably compared with state-of-the-art solvers.more » « less
-
Abstract Let be a simple graph and be the chromatic index of . We call a ‐critical graphif for every edge of , where is maximum degree of . Let be an edge of ‐critical graph and be an (proper) edge ‐coloring of . Ane‐fanis a sequence of alternating vertices and distinct edges such that edge is incident with or , is another endvertex of and is missing at a vertex before for each with . In this paper, we prove that if , where and denote the degrees of vertices and , respectively, then colors missing at different vertices of are distinct. Clearly, a Vizing fan is an ‐fan with the restricting that all edges being incident with one fixed endvertex of edge . This result gives a common generalization of several recently developed new results on multifan, double fan, Kierstead path of four vertices, and broom. By treating some colors of edges incident with vertices of low degrees as missing colors, Kostochka and Stiebitz introduced ‐fan. In this paper, we also generalize the ‐fan from centered at one vertex to one edge.more » « less
-
Abstract A conjecture of Milena Mihail and Umesh Vazirani (Proc. 24th Annu. ACM Symp. Theory Comput., ACM, Victoria, BC, 1992, pp. 26–38.) states that the edge expansion of the graph of every polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a polytope in is greater than one over some polynomial function of . This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of arandompolytope in is at least with high probability.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/jgt.23155
