On an f-coloring generalization of linear arboricity of multigraphs

DOI10.1016/J.DISC.2023.113777MaRDI QIDQ6184546zbMATH OpenOpenAlexFDO

Authors Ronen Wdowinski

Publication date 25 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

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

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)