skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 10:00 PM ET on Friday, February 6 until 10:00 AM ET on Saturday, February 7 due to maintenance. We apologize for the inconvenience.


Title: Proof of the Goldberg–Seymour conjecture on edge–colorings of multigraphs
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
Award ID(s):
2348740 2246292 2001130
PAR ID:
10639889
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer
Date Published:
Journal Name:
Journal of Combinatorial Optimization
Volume:
50
Issue:
3
ISSN:
1382-6905
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Let G ( k ) {G(k)}denote the least numbershaving the property that everysufficiently large natural number is the sum of at mostspositive integralk-th powers.Then for all k {k\in\mathbb{N}}, one has G ( k ) k ( log k + 4.20032 ) . G(k)\leqslant\lceil k(\log k+4.20032)\rceil. Our new methods improve on all bounds available hitherto when k 14 {k\geqslant 14}. 
    more » « less
  2. Abstract A model based on a$$U(1)_{T^3_R}$$ U ( 1 ) T R 3 extension of the Standard Model can address the mass hierarchy between generations of fermions, explain thermal dark matter abundance, and the muon$$g - 2$$ g - 2 ,$$R_{(D)}$$ R ( D ) , and$$R_{(D^*)}$$ R ( D ) anomalies. The model contains a light scalar boson$$\phi '$$ ϕ and a heavy vector-like quark$$\chi _\textrm{u}$$ χ u that can be probed at CERN’s large hadron collider (LHC). We perform a phenomenology study on the production of$$\phi '$$ ϕ and$${\chi }_u$$ χ u particles from proton–proton$$(\textrm{pp})$$ ( pp ) collisions at the LHC at$$\sqrt{s}=13.6$$ s = 13.6 TeV, primarily through$$g{-g}$$ g - g and$$t{-\chi _\textrm{u}}$$ t - χ u fusion. We work under a simplified model approach and directly take the$$\chi _\textrm{u}$$ χ u and$$\phi '$$ ϕ masses as free parameters. We perform a phenomenological analysis considering$$\chi _\textrm{u}$$ χ u final states to b-quarks, muons, and neutrinos, and$$\phi '$$ ϕ decays to$$\mu ^+\mu ^-$$ μ + μ - . A machine learning algorithm is used to maximize the signal sensitivity, considering an integrated luminosity of 3000$$\text {fb}^{-1}$$ fb - 1 . The proposed methodology can be a key mode for discovery over a large mass range, including low masses, traditionally considered difficult due to experimental constraints. 
    more » « less
  3. Abstract The purpose of this paper is to introduce and study the following graph-theoretic paradigm. Let$$ \begin{align*}T_Kf(x)=\int K(x,y) f(y) d\mu(y),\end{align*} $$where$$f: X \to {\Bbb R}$$,Xa set, finite or infinite, andKand$$\mu $$denote a suitable kernel and a measure, respectively. Given a connected ordered graphGonnvertices, consider the multi-linear form$$ \begin{align*}\Lambda_G(f_1,f_2, \dots, f_n)=\int_{x^1, \dots, x^n \in X} \ \prod_{(i,j) \in {\mathcal E}(G)} K(x^i,x^j) \prod_{l=1}^n f_l(x^l) d\mu(x^l),\end{align*} $$where$${\mathcal E}(G)$$is the edge set ofG. Define$$\Lambda _G(p_1, \ldots , p_n)$$as the smallest constant$$C>0$$such that the inequality(0.1)$$ \begin{align} \Lambda_G(f_1, \dots, f_n) \leq C \prod_{i=1}^n {||f_i||}_{L^{p_i}(X, \mu)} \end{align} $$holds for all nonnegative real-valued functions$$f_i$$,$$1\le i\le n$$, onX. The basic question is, how does the structure ofGand the mapping properties of the operator$$T_K$$influence the sharp exponents in (0.1). In this paper, this question is investigated mainly in the case$$X={\Bbb F}_q^d$$, thed-dimensional vector space over the field withqelements,$$K(x^i,x^j)$$is the indicator function of the sphere evaluated at$$x^i-x^j$$, and connected graphsGwith at most four vertices. 
    more » « less
  4. Abstract We study the production of$$D^0$$ D 0 meson inp+pandp-Pb collisions using the improved AMPT model considering both coalescence and independent fragmentation of charm quarks after the Cronin broadening is included. After a detailed discussion of the improvements implemented in the AMPT model for heavy quark production, we show that the modified AMPT model can provide a good description of$$D^0$$ D 0 meson spectra inp-Pb collisions, the$$Q_{\textrm{pPb}}$$ Q pPb data at different centralities and$$R_{\textrm{pPb}}$$ R pPb data in both mid- and forward (backward) rapidities. We also studied the effects of nuclear shadowing and parton cascade on the rapidity dependence of$$D^{0}$$ D 0 meson production and$$R_{\textrm{pPb}}$$ R pPb . Our results indicate that using the same strength of the Cronin effect (i.e$$\delta $$ δ value) as that obtained from the mid-rapidity data leads to a considerable overestimation of the$$D^0$$ D 0 meson spectra and$$R_{\textrm{pPb}}$$ R pPb data at high$$p_{\textrm{T}}$$ p T in the backward rapidity. As a result, the$$\delta $$ δ is determined via a$$\chi ^2$$ χ 2 fitting of the$$R_{\textrm{pPb}}$$ R pPb data across various rapidities. This work lays the foundation for a better understanding of cold-nuclear-matter (CNM) effects in relativistic heavy-ion collisions. 
    more » « less
  5. Let $$G$$ be a multigraph. A subset $$F$$ of $E(G)$ is an edge cover of $$G$$ if every vertex of $$G$$ is incident to an edge of $$F$$. The cover index, $$\xi(G)$$, is the largest number of edge covers into which the edges of $$G$$ can be partitioned. Clearly $$\xi(G) \le \delta(G)$$, the minimum degree of $$G$$. For $$U\subseteq V(G)$$, denote by $E^+(U)$ the set of edges incident to a vertex of $$U$$. When $|U|$ is odd, to cover all the vertices of $$U$$, any edge cover needs to contain at least $(|U|+1)/2$ edges from $E^+(U)$, indicating $$ \xi(G) \le |E^+(U)|/ ((|U|+1)/2)$$. Let $$\rho_c(G)$$, the co-density of $$G$$, be defined as the minimum of $|E^+(U)|/((|U|+1)/2)$ ranging over all $$U\subseteq V(G)$$, where $$|U| \ge 3$$ and $|U|$ is odd. Then $$\rho_c(G)$$ provides another upper bound on $$\xi(G)$$. Thus $$\xi(G) \le \min\{\delta(G), \lfloor \rho_c(G) \rfloor \}$$. For a lower bound on $$\xi(G)$$, in 1978, Gupta conjectured that $$\xi(G) \ge \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \}$$. Gupta himself verified the conjecture for simple graphs, and Cao et al. recently verified this conjecture when $$\rho_c(G)$$ is not an integer. In this paper, we confirm the conjecture when the maximum multiplicity of $$G$$ is at most two or $$ \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \} \le 6$$. The proof relies on a newly established result on edge colorings. The result holds independent interest and has the potential to significantly contribute towards resolving the conjecture entirely. 
    more » « less