On an f-coloring generalization of linear arboricity of multigraphs

DOI10.1016/J.DISC.2023.113777arXiv2301.09933OpenAlexW4388473630MaRDI QIDQ6184546FDOQ6184546

Authors: Ronen Wdowinski 

Publication date: 25 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Given a multigraph $G$ and function $f:V(G)ightarrowmathbb{Z}_{ge2}$ on its vertices, a degree-$f$ subgraph of $G$ is a spanning subgraph in which every vertex $v$ has degree at most $f(v)$. The degree-$f$ arboricity $a_f(G)$ of $G$ is the minimum number of colors required to edge-color $G$ into degree-$f$ forests. At least for constant $f$, Truszczy'nski conjectured that $a_f(G)lemaxDelt{a}_f(G)+1,a(G)$ for every multigraph $G$, where $Delt{a}_f(G)=ma{x}_{vinV(G)}lceild(v)/f(v)ceil$ and $a(G)$ is the usual arboricity of $G$. This is a strong generalization of the Linear Arboricity Conjecture due to Akiyama, Exoo, and Harary. In this paper, we disprove Truszczy'nski's conjecture in a strong sense for general multigraphs. On the other hand, extending known results for linear arboricity, we prove that the conjecture holds for simple graphs with sufficiently large girth, and that it holds for all simple graphs asymptotically. More strongly, we prove these partial results in the setting of directed graphs, where the color classes are required to be analogously defined degree-$f$ branchings.

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

Recommendations

• Orientation‐based edge‐colorings and linear arboricity of multigraphs
• scientific article; zbMATH DE number 4101233
• The linear arboricity of graphs
• scientific article; zbMATH DE number 566421
• Decompositions of graphs into forests with bounded maximum degree

zbMATH Keywords

fractional arboricitylinear arboricitybranchings\(f\)-coloringspseudoarboricity

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• On the degrees of the vertices of a directed graph
• Decomposition of Finite Graphs Into Forests
• On two minimax theorems in graph
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Short Tours through Large Linear Forests
• A generalization of edge-coloring in graphs
• The linear arboricity of graphs
• The linear arboricity of series-parallel graphs
• The linear arboricity of planar graphs of maximum degree seven is four
• The linear arboricity of some regular graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Covering and packing in graphs IV: Linear arboricity
• Complexité de l'arboricité linéaire d'un graphe
• Title not available (Why is that?)
• COVERING AND PACKING IN GRAPHS, I.
• Linear arboricity and linear \(k\)-arboricity of regular graphs
• Characterizations of graphs having orientations satisfying local degree restrictions
• Eigenvalues of \(K_{1,k}\)-free graphs and the connectivity of their independence complexes
• Extremal problems for transversals in graphs with bounded degree
• Towards the linear arboricity conjecture
• Title not available (Why is that?)
• On the f-coloring of multigraphs
• A note on vertex list colouring
• Decompositions of graphs into forests with bounded maximum degree
• Title not available (Why is that?)
• Linear arboricity of digraphs
• Probabilistic methods in coloring and decomposition problems
• Acyclic edge-colorings of sparse graphs
• An improved bound for the linear arboricity conjecture
• Linear arboricity of regular digraphs
• Linear arboricity of degenerate graphs
• Orientation‐based edge‐colorings and linear arboricity of multigraphs

This page was built for publication: On an \(f\)-coloring generalization of linear arboricity of multigraphs

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