Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProof of the Goldberg-Seymour Conjecture on Edge-Colorings of Multigraphs
72
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a multigraph $G=(V,E)$, the {em edge-coloring problem} (ECP) is to color the edges of $G$ with 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 called the {em fractional edge-coloring problem} (FECP). In the literature, the optimal value of ECP (resp. FECP) is called the {em chromatic index} (resp. {em fractional chromatic index}) of $G$, denoted by $chi(G)$ (resp. $chi^*(G)$). Let $Delta(G)$ be the maximum degree of $G$ and let [Gamma(G)=max Big{frac{2|E(U)|}{|U|-1}:,, U subseteq V, ,, |U|ge 3 hskip 2mm {rm and hskip 2mm odd} Big},] where $E(U)$ is the set of all edges of $G$ with both ends in $U$. 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 1970s Goldberg and Seymour independently conjectured that $chi(G) le max{Delta(G)+1, , lceil Gamma(G) rceil}$. Over the past four decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated a significant 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 Vizings theorem on edge-colorings of simple graphs, a fundamental result in graph theory, holds for multigraphs; second, although it is $NP$-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 multigraph $G$ satisfies $chi(G)-chi^*(G) le 1$, so FECP has a fascinating integer rounding property.
rate research
Read More
Appearing in different format, Gupta,(1967), Goldberg,(1973), Andersen,(1977), and Seymour,(1979) conjectured that if $G$ is an edge-$k$-critical graph with $k ge Delta +1$, then $|V(G)|$ is odd and, for every edge $e$, $E(G-e)$ is a union of disjoint near-perfect matchings, where $Delta$ denotes the maximum degree of $G$. Tashkinov tree method shows that critical graphs contain a subgraph with two important properties named closed and elementary. Recently, efforts have been made in extending graphs beyond Tashkinov trees. However, these results can only keep one of the two essential properties. In this paper, we developed techniques to extend Tashkinov trees to larger subgraphs with both properties. Applying our result, we have improved almost all known results towards Goldbergs conjecture. In particular, we showed that Goldbergs conjecture holds for graph $G$ with $|V(G)| le 39$ and $|Delta(G)| le 39$ and Jacobsens equivalent conjecture holds for $m le 39$ while the previous known bound is $23$.
Komlos conjectured in 1981 that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large. In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify.
A proper edge coloring of a graph $G$ with colors $1,2,dots,t$ is called a emph{cyclic interval $t$-coloring} if for each vertex $v$ of $G$ the edges incident to $v$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. We prove that a bipartite graph $G$ with even maximum degree $Delta(G)geq 4$ admits a cyclic interval $Delta(G)$-coloring if for every vertex $v$ the degree $d_G(v)$ satisfies either $d_G(v)geq Delta(G)-2$ or $d_G(v)leq 2$. We also prove that every Eulerian bipartite graph $G$ with maximum degree at most $8$ has a cyclic interval coloring. Some results are obtained for $(a,b)$-biregular graphs, that is, bipartite graphs with the vertices in one part all having degree $a$ and the vertices in the other part all having degree $b$; it has been conjectured that all these have cyclic interval colorings. We show that all $(4,7)$-biregular graphs as well as all $(2r-2,2r)$-biregular ($rgeq 2$) graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this settles in the affirmative, a conjecture of Petrosyan and Mkhitaryan.
A $k$-improper edge coloring of a graph $G$ is a mapping $alpha:E(G)longrightarrow mathbb{N}$ such that at most $k$ edges of $G$ with a common endpoint have the same color. An improper edge coloring of a graph $G$ is called an improper interval edge coloring if the colors of the edges incident to each vertex of $G$ form an integral interval. In this paper we introduce and investigate a new notion, the interval coloring impropriety (or just impropriety) of a graph $G$ defined as the smallest $k$ such that $G$ has a $k$-improper interval edge coloring; we denote the smallest such $k$ by $mu_{mathrm{int}}(G)$. We prove upper bounds on $mu_{mathrm{int}}(G)$ for general graphs $G$ and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine $mu_{mathrm{int}}(G)$ exactly for $G$ belonging to some particular classes of graphs. Furthermore, we provide several families of graphs with large impropriety; in particular, we prove that for each positive integer $k$, there exists a graph $G$ with $mu_{mathrm{int}}(G) =k$. Finally, for graphs with at least two vertices we prove a new upper bound on the number of colors used in an improper interval edge coloring.
A proper edge-coloring of a graph $G$ with colors $1,ldots,t$ is called an emph{interval cyclic $t$-coloring} if all colors are used, and the edges incident to each vertex $vin V(G)$ are colored by $d_{G}(v)$ consecutive colors modulo $t$, where $d_{G}(v)$ is the degree of a vertex $v$ in $G$. A graph $G$ is emph{interval cyclically colorable} if it has an interval cyclic $t$-coloring for some positive integer $t$. The set of all interval cyclically colorable graphs is denoted by $mathfrak{N}_{c}$. For a graph $Gin mathfrak{N}_{c}$, the least and the greatest values of $t$ for which it has an interval cyclic $t$-coloring are denoted by $w_{c}(G)$ and $W_{c}(G)$, respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if $G$ is a triangle-free graph with at least two vertices and $Gin mathfrak{N}_{c}$, then $W_{c}(G)leq vert V(G)vert +Delta(G)-2$. We also obtain bounds on $w_{c}(G)$ and $W_{c}(G)$ for various classes of graphs. Finally, we give some methods for constructing of interval cyclically non-colorable graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
