List-Coloring Squares of Sparse Subcubic Graphs

DOI10.1137/050634049zbMath1159.05018OpenAlexW2031929504MaRDI QIDQ3614198

Riste Škrekovski, Zdeněk Dvořák, Martin Tancer

Publication date: 16 March 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/d87acbecd4b6a7a374c42837184d5cc120679812

zbMATH Keywords

planar graphschromatic numberNP-completesparse graphslist coloringsquare of a graphchoosability numbersparse subcubic graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (14)

Graph \(r\)-hued colorings -- a survey ⋮ Locally injective \(k\)-colourings of planar graphs ⋮ Are there any good digraph width measures? ⋮ A survey on the cyclic coloring and its relaxations ⋮ Linear colorings of subcubic graphs ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ List 2-facial 5-colorability of plane graphs with girth at least 12 ⋮ Distance-two colourings of Barnette graphs ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ Unnamed Item ⋮ The complexity of frugal colouring ⋮ Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\) ⋮ The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes ⋮ On the Complexity of Planar Covering of Small Graphs

This page was built for publication: List-Coloring Squares of Sparse Subcubic Graphs