Orientation‐based edge‐colorings and linear arboricity of multigraphs

DOI10.1002/JGT.22890MaRDI QIDQ6094040zbMATH OpenOpenAlexFDO

Authors Ronen Wdowinski

Publication date 9 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.11816

zbMATH Keywords

orientationsedge-coloringlinear arboricity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: 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.

Recommendations

• Edge coloring multigraphs without small dense subsets
• On a theorem of Goldberg
• Approximating the chromatic index of multigraphs
• On characterizing Vizing's edge colouring bound
• On the chromatic index of multigraphs and a conjecture of Seymour (I)

Cites work

• scientific article; zbMATH DE number 3989394 (Why is no real title available?)
• scientific article; zbMATH DE number 4101233 (Why is no real title available?)
• scientific article; zbMATH DE number 3717365 (Why is no real title available?)
• scientific article; zbMATH DE number 3470445 (Why is no real title available?)
• scientific article; zbMATH DE number 1560509 (Why is no real title available?)
• A Theorem on Coloring the Lines of a Network
• A generalization of edge-coloring in graphs
• A note on list arboricity
• Acyclic edge-colorings of sparse graphs
• Approximating the chromatic index of multigraphs
• Asymptotically good list-colorings
• COVERING AND PACKING IN GRAPHS, I.
• Characterizations of graphs having orientations satisfying local degree restrictions
• Chromatic index determined by fractional chromatic index
• Decomposition of Finite Graphs Into Forests
• Forests, frames, and games: Algorithms for matroid sums and applications
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• Graph edge colouring: Tashkinov trees and Goldberg's conjecture
• Graph theory
• Linear arboricity of digraphs
• List-colourings of graphs
• Minimum partition of a matroid into independent subsets
• NP-completeness of some problems of partitioning and covering in graphs
• Note on linear arboricity of graphs with large girth
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On edge-colorings of graphs.
• On the degrees of the vertices of a directed graph
• On the f-coloring of multigraphs
• Some results on linear arboricity
• The NP-Completeness of Edge-Coloring
• The conjunction of the linear arboricity conjecture and Lovász's path partition theorem
• The list chromatic index of a bipartite multigraph
• Upper bound for linear arboricity

Cited in

(3)

• On an \(f\)-coloring generalization of linear arboricity of multigraphs
• Linear arboricity of degenerate graphs
• A decomposition method on solving the linear arboricity conjecture

This page was built for publication: Orientation‐based edge‐colorings and linear arboricity of multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094040)