Orientation‐based edge‐colorings and linear arboricity of multigraphs

DOI10.1002/JGT.22890zbMATH Open1522.05145arXiv2108.11816OpenAlexW3195612562MaRDI QIDQ6094040FDOQ6094040

Authors: Ronen Wdowinski 

Publication date: 9 October 2023

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

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.

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

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)

zbMATH Keywords

orientationsedge-coloringlinear arboricity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

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

Cited In (3)

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

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)