On Equitable List Arboricity of Graphs

zbMATH Open1468.05079arXiv2008.08926MaRDI QIDQ5000322FDOQ5000322

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

Publication date: 12 July 2021

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).

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)

Cites Work

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

Cited In (4)

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

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)