Vertex arboricity of toroidal graphs with a forbidden cycle

DOI10.1016/J.DISC.2014.06.011MaRDI QIDQ400411zbMATH OpenOpenAlexFDO

Authors Ilkyoo Choi, Haihui Zhang

Publication date 21 August 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dischargingtoroidal graphsvertex arboricity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The vertex arboricity $a(G)$ of a graph $G$ is the minimum $k$ such that $V(G)$ can be partitioned into $k$ sets where each set induces a forest. For a planar graph $G$, it is known that $a(G)leq3$. In two recent papers, it was proved that planar graphs without $k$-cycles for some $kin3,4,5,6,7$ have vertex arboricity at most 2. For a toroidal graph $G$, it is known that $a(G)leq4$. Let us consider the following question: do toroidal graphs without $k$-cycles have vertex arboricity at most 2? It was known that the question is true for k=3, and recently, Zhang proved the question is true for $k=5$. Since a complete graph on 5 vertices is a toroidal graph without any $k$-cycles for $kgeq6$ and has vertex arboricity at least three, the only unknown case was k=4. We solve this case in the affirmative; namely, we show that toroidal graphs without 4-cycles have vertex arboricity at most 2.

Recommendations

• Vertex-arboricity of toroidal graphs without \(K_5^-\) and \(6\)-cycles
• A note on the list vertex arboricity of toroidal graphs
• On list vertex 2-arboricity of toroidal graphs without cycles of specific length
• Linear 2-arboricity of toroidal graphs
• List vertex-arboricity of toroidal graphs without 4-cycles adjacent to 3-cycles
• scientific article; zbMATH DE number 7366688
• (3, 1)-choosability of toroidal graphs with some forbidden short cycles
• scientific article; zbMATH DE number 3887724
• On enumeration of a class of toroidal graphs
• On the cop number of toroidal graphs

Cites work

• A Note on the Vertex Arboricity of a Graph
• An Analogue to the Heawood Map-Colouring Problem
• B-sets and planar maps
• Critical Point-Arboritic Graphs
• On list vertex 2-arboricity of toroidal graphs without cycles of specific length
• On the vertex-arboricity of planar graphs
• On the vertex-arboricity of planar graphs without 7-cycles
• Point-Arboricity and Girth
• The point-arboricity of a graph
• The Point-Arboricity of Planar Graphs
• Vertex-arboricity of planar graphs without intersecting triangles

Cited in

(14)

• Vertex arboricity of planar graphs without intersecting 5-cycles
• A note on the list vertex arboricity of toroidal graphs
• Vertex-arboricity of toroidal graphs without \(K_5^-\) and \(6\)-cycles
• Cover and variable degeneracy
• Two sufficient conditions for a planar graph to be list vertex-2-arborable
• A note of vertex arboricity of planar graphs without 4-cycles intersecting with 6-cycles
• On list vertex 2-arboricity of toroidal graphs without cycles of specific length
• On the vertex-arboricity of \(K_5\)-minor-free graphs of diameter 2
• List vertex arboricity of planar graphs without 5-cycles intersecting with 6-cycles
• List vertex-arboricity of toroidal graphs without 4-cycles adjacent to 3-cycles
• scientific article; zbMATH DE number 7366688 (Why is no real title available?)
• Toroidal graphs without 3-cycles adjacent to 5-cycles have list vertex-arboricity at most 2
• Vertex arboricity of graphs embedded in a surface of non-negative Euler characteristic
• Variable degeneracy on toroidal graphs

This page was built for publication: Vertex arboricity of toroidal graphs with a forbidden cycle

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