2021/08/26 by Ronen Wdowinski, Wdowinski, Ronen
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.2108.11816
arxiv created 2021/08/26 · openalex publication_date 2021/08/26 · arxiv updated 2021/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Goldberg-Seymour Conjecture for f-colorings states that the f-chromatic index of a loopless multigraph is essentially determined by either a maximum degree or a maximum density parameter. We introduce an oriented version of f-colorings, where now each color class of the edge-coloring is required to be orientable in such a way that every vertex v has indegree and outdegree at most some specified values g(v) and h(v). We prove that the associated (g,h)-oriented chromatic index satisfies a Goldberg-Seymour formula. We then present simple applications of this result to variations of f-colorings. In particular, we show that the Linear Arboricity Conjecture holds for k-degenerate loopless multigraphs when the maximum degree is at least 4k-2, improving a bound recently announced by Chen, Hao, and Yu for simple graphs. Finally, we demonstrate that the (g,h)-oriented chromatic index is always equal to its list coloring analogue.