Every toroidal graph without adjacent triangles is \((4,1)^{*}\)-choosable

DOI10.1016/j.dam.2006.04.042zbMath1107.05039MaRDI QIDQ858302

Haihui Zhang, Bao-Gang Xu

Publication date: 9 January 2007

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

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.042

zbMATH Keywords

choosability; linear algorithm

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Improper Choosability and Property B, \((3, 1)^*\)-choosability of graphs of nonnegative characteristic without intersecting short cycles, A \((3,1)^\ast\)-choosable theorem on planar graphs, On \((3, 1)^\ast\)-choosability of planar graphs without adjacent short cycles, A \((3,1)^*\)-choosable theorem on toroidal graphs, A note on list improper coloring of plane graphs, Acyclic improper choosability of subcubic graphs, (3, 1)-choosability of toroidal graphs with some forbidden short cycles, Improper choosability of graphs of nonnegative characteristic, ON (3, 1)*-CHOOSABILITY OF TOROIDAL GRAPHS

Cites Work

• Unnamed Item
• Contractible edges in 3-connected graphs
• On structure of graphs embedded on surfaces of nonnegative characteristic with application to choosability
• On structure of some plane graphs with application to choosability
• On vertex types and cyclic colourings of 3-connected plane graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• List Improper Colourings of Planar Graphs
• Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9
• Choosability and Edge Choosability of Planar Graphs without Intersecting Triangles
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• A note on list improper coloring planar graphs
• \((4m,m)\)-choosability of plane graphs