Variable degeneracy: Extensions of Brooks' and Gallai's theorems

DOI10.1016/S0012-365X(99)00221-6zbMath0949.05029OpenAlexW2100628151MaRDI QIDQ1972133

Oleg V. Borodin, Alexandr V. Kostochka, Bjarne Toft

Publication date: 3 December 2000

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(99)00221-6

zbMATH Keywords

colouringchromatic numberlist chromatic numberBrooks' theoremlist colouringvertex functionpoint partition numbersGallai's theoremvariable degeneracylist point arboricity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (29)

Two sufficient conditions for a planar graph to be list vertex-2-arborable ⋮ LIST POINT ARBORICITY OF GRAPHS ⋮ List vertex-arboricity of toroidal graphs without 4-cycles adjacent to 3-cycles ⋮ Point partition numbers: decomposable and indecomposable critical graphs ⋮ Digraphs and Variable Degeneracy ⋮ Brooks' Theorem and Beyond ⋮ On Equitable List Arboricity of Graphs ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Partitions of hypergraphs under variable degeneracy constraints ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Signed colouring and list colouring of k‐chromatic graphs ⋮ Partitioning into degenerate graphs in linear time ⋮ A generalization of some results on list coloring and DP-coloring ⋮ Generalized DP-colorings of graphs ⋮ Sparse Graphs Are Near-Bipartite ⋮ List strong linear 2-arboricity of sparse graphs ⋮ A weaker version of a conjecture on list vertex arboricity of graphs ⋮ Partitioning a graph into degenerate subgraphs ⋮ Satisfactory graph partition, variants, and generalizations ⋮ List total arboricity of 2-degenerate graphs ⋮ Vertex partition of hypergraphs and maximum degenerate subhypergraphs ⋮ A note on the list vertex arboricity of toroidal graphs ⋮ An analogue of DP-coloring for variable degeneracy and its applications ⋮ Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable ⋮ Vertex-arboricity of toroidal graphs without \(K_5^-\) and \(6\)-cycles ⋮ Cover and variable degeneracy ⋮ List point arboricity of dense graphs ⋮ Vertex arboricity of planar graphs without chordal 6-cycles ⋮ Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without 4-cycles and 7-cycles

This page was built for publication: Variable degeneracy: Extensions of Brooks' and Gallai's theorems