On equitable list arboricity of graphs

zbMATH1468.05079MaRDI QIDQ5000322FDOQ5000322

Authors Hemanshu Kaul, Michael J. Pelsmajer, J. A. Mudrock

Publication date 12 July 2021

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

zbMATH Keywords

equitable list coloringequitably \(k\)-list arborable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Equitable list arboricity, introduced by Zhang in 2016, generalizes the notion of equitable list coloring by requiring the subgraph induced by each color class to be acyclic (instead of edgeless) in addition to the usual upper bound on the size of each color class. Graph $G$ is equitably $k$-list arborable if an equitable, arborable list coloring of $G$ exists for every list assignment for $G$ that associates with each vertex in $G$ a list of $k$ available colors. Zhang conjectured that any graph $G$ is equitably $k$-list arborable for each $k$ satisfying $kgeqlceil(1+Delta(G))/2ceil$. We verify this conjecture for powers of cycles by applying a new lemma which is a general tool for extending partial equitable, arborable list colorings. We also propose a stronger version of Zhang's Conjecture for certain connected graphs: any connected graph $G$ is equitably $k$-list arborable for each $k$ satisfying $kgeqlceilDelta(G)/2ceil$ provided $G$ is neither a cycle nor a complete graph of odd order. We verify this stronger version of Zhang's Conjecture for powers of paths, 2-degenerate graphs, and certain other graphs. We also show that if $G$ is equitably $k$-list arborable it does not necessarily follow that $G$ is equitably $(k+1)$-list arborable which addresses a question of Drgas-Burchardt, Furmanczyk, and Sidorowicz (2018).

Recommendations

• Equitable list vertex colourability and arboricity of grids
• Equitable list point arboricity of graphs
• Total equitable list coloring
• Equitable list coloring of graphs
• A conjecture on equitable vertex arboricity of graphs

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 1302199 (Why is no real title available?)
• scientific article; zbMATH DE number 1046311 (Why is no real title available?)
• scientific article; zbMATH DE number 3222646 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A conjecture on equitable vertex arboricity of graphs
• A list analogue of equitable coloring
• A note on the equitable choosability of complete bipartite graphs
• Equitable Coloring
• Equitable and equitable list colorings of graphs
• Equitable coloring and equitable choosability of graphs with small maximum average degree
• Equitable coloring and equitable choosability of planar graphs without chordal 4- and 6-cycles
• Equitable coloring and the maximum degree
• Equitable improper choosability of graphs
• Equitable list coloring of graphs with bounded degree
• Equitable list coloring of planar graphs without 4- and 6-cycles
• Equitable list colorings of planar graphs without short cycles
• Equitable list point arboricity of graphs
• Equitable list tree-coloring of bounded treewidth graphs
• Equitable list vertex colourability and arboricity of grids
• Equitable list-coloring for \(C_{5}\)-free plane graphs without adjacent triangles
• Equitable partition of graphs into induced linear forests
• Equitable partition of plane graphs with independent crossings into induced forests
• Equitable vertex arboricity of graphs
• Equitable vertex arboricity of subcubic graphs
• Generalized list colourings of graphs
• On equitable and equitable list colorings of series-parallel graphs
• On equitable coloring of bipartite graphs
• On list equitable total colorings of the generalized theta graph
• The Point-Arboricity of Planar Graphs
• Theoretical aspects of equitable partition of networks into sparse modules
• Total equitable list coloring
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems

Cited in

(5)

• Equitable list tree-coloring of bounded treewidth graphs
• A note on list arboricity
• Equitable vertex arboricity conjecture holds for graphs with low degeneracy
• Equitable list vertex colourability and arboricity of grids
• Equitable list point arboricity of graphs

This page was built for publication: On equitable list arboricity of graphs

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