Variable degeneracy: Extensions of Brooks' and Gallai's theorems
DOI10.1016/S0012-365X(99)00221-6zbMATH Open0949.05029OpenAlexW2100628151MaRDI QIDQ1972133FDOQ1972133
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
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
chromatic numbercolouringBrooks' theoremlist colouringvertex functionlist chromatic numberGallai's theorempoint partition numbersvariable degeneracylist point arboricity
Cited In (31)
- Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable
- Vertex partition of hypergraphs and maximum degenerate subhypergraphs
- Sparse graphs are near-bipartite
- List point arboricity of graphs
- Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without 4-cycles and 7-cycles
- On equitable list arboricity of graphs
- Digraphs and variable degeneracy
- Two sufficient conditions for a planar graph to be list vertex-2-arborable
- List total arboricity of 2-degenerate graphs
- List vertex-arboricity of toroidal graphs without 4-cycles adjacent to 3-cycles
- A note on the list vertex arboricity of toroidal graphs
- Point partition numbers: decomposable and indecomposable critical graphs
- Partitioning a graph into degenerate subgraphs
- Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
- Vertex-arboricity of toroidal graphs without \(K_5^-\) and \(6\)-cycles
- Signed colouring and list colouring of k‐chromatic graphs
- A note on graph coloring extensions and list-colorings
- Brooks' Theorem
- List strong linear 2-arboricity of sparse graphs
- Satisfactory graph partition, variants, and generalizations
- Vertex arboricity of planar graphs without chordal 6-cycles
- Generalized DP-colorings of graphs
- An analogue of DP-coloring for variable degeneracy and its applications
- Partitions of hypergraphs under variable degeneracy constraints
- Partitioning into degenerate graphs in linear time
- Graphs with \(\chi=\Delta\) have big cliques
- Cover and variable degeneracy
- A weaker version of a conjecture on list vertex arboricity of graphs
- A generalization of some results on list coloring and DP-coloring
- List point arboricity of dense graphs
- Brooks' Theorem and Beyond
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)
