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

DOI10.1016/S0012-365X(99)00221-6MaRDI QIDQ1972133zbMATH OpenOpenAlexFDO

Authors Oleg V. Borodin, Alexandr 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

Brooks' theoremchromatic numbercolouringGallai's theoremlist chromatic numberlist colouringlist point arboricitypoint partition numbersvariable degeneracyvertex function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• A list version of Dirac's theorem on the number of edges in colour-critical graphs
• Brook's theorem
• Brooks' theorem for generalized dart graphs
• A note on graph coloring extensions and list-colorings
• Gallai's theorem for list coloring of digraphs
• Generalized DP-colorings of graphs
• scientific article; zbMATH DE number 1452400
• An NC algorithm for Brooks' theorem
• The colour theorems of Brooks and Gallai extended
• A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs

Cited in

(33)

• List point arboricity of dense graphs
• The colour theorems of Brooks and Gallai extended
• A note on the list vertex arboricity of toroidal graphs
• A note on graph coloring extensions and list-colorings
• Partitioning a graph into degenerate subgraphs
• An analogue of DP-coloring for variable degeneracy and its applications
• Vertex-arboricity of toroidal graphs without \(K_5^-\) and \(6\)-cycles
• Cover and variable degeneracy
• Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without 4-cycles and 7-cycles
• Two sufficient conditions for a planar graph to be list vertex-2-arborable
• Point partition numbers: decomposable and indecomposable critical graphs
• A generalization of some results on list coloring and DP-coloring
• Vertex arboricity of planar graphs without chordal 6-cycles
• List vertex-arboricity of toroidal graphs without 4-cycles adjacent to 3-cycles
• Graphs with \(\chi=\Delta\) have big cliques
• List strong linear 2-arboricity of sparse graphs
• List point arboricity of graphs
• Brooks' Theorem and Beyond
• Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable
• Vertex partition of hypergraphs and maximum degenerate subhypergraphs
• A weaker version of a conjecture on list vertex arboricity of graphs
• On equitable list arboricity of graphs
• Digraphs and variable degeneracy
• Sparse graphs are near-bipartite
• 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
• Generalized DP-colorings of graphs
• Brooks' Theorem
• Brooks-type colourings of digraphs in linear time
• List total arboricity of 2-degenerate graphs
• Satisfactory graph partition, variants, and generalizations

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

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