Premium
Orientation‐based edge‐colorings and linear arboricity of multigraphs
Author(s) -
Wdowinski Ronen
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22890
Subject(s) - edge coloring , combinatorics , mathematics , arboricity , multigraph , conjecture , simple (philosophy) , upper and lower bounds , vertex (graph theory) , list coloring , chromatic scale , discrete mathematics , graph , planar graph , philosophy , epistemology , mathematical analysis , line graph , graph power
The Goldberg–Seymour Conjecture forf $f$ ‐colorings states that thef $f$ ‐chromatic index of a loopless multigraph is essentially determined by either a weighted maximum degree or a weighted maximum density parameter. We introduce an oriented version off $f$ ‐colorings, where now each color class of the edge‐coloring is required to be orientable in such a way that every vertexv $v$ has indegree and outdegree at most some specified valuesg ( v )$g(v)$ andh ( v )$h(v)$ . We prove that the associated( g , h )$(g,h)$ ‐oriented chromatic index satisfies a Goldberg–Seymour formula. We then present simple applications of this result to variations off $f$ ‐colorings. In particular, we show that the Linear Arboricity Conjecture holds fork $k$ ‐degenerate loopless multigraphs when the maximum degree is at least4 k − 2 $4k-2$ , improving a recent bound by Chen, Hao, and Yu for simple graphs. Finally, we demonstrate that the( g , h )$(g,h)$ ‐oriented chromatic index is always equal to its list coloring analogue.