Brooks' Theorem and Beyond
From MaRDI portal
Publication:3466339
DOI10.1002/jgt.21847zbMath1330.05061arXiv1403.0479OpenAlexW1581277026MaRDI QIDQ3466339
Daniel W. Cranston, Landon Rabern
Publication date: 1 February 2016
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1403.0479
Related Items
Digraphs and Variable Degeneracy ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Extremal decompositions for Nordhaus-Gaddum theorems ⋮ Four proofs of the directed Brooks' theorem ⋮ Yet another proof of Brooks' theorem ⋮ Special issue in honour of Landon Rabern ⋮ Dirac's theorem on chordal graphs implies Brooks' theorem ⋮ Brooks' theorem with forbidden colors ⋮ The chromatic number of a signed graph ⋮ Improved distributed \(\Delta\)-coloring ⋮ A short proof of Brooks’ Theorem for vertex arboricity ⋮ Chromatic Ramsey number of acyclic hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A unified proof of Brooks' theorem and Catlin's theorem
- A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
- Brooks' theorem via the Alon-Tarsi theorem
- Lower bound of the Hadwiger number of graphs by their average degree
- On equitable \(\Delta\)-coloring of graphs with low average degree
- On Schmerl's effective version of Brooks' theorem
- Colorings and orientations of graphs
- Three short proofs in graph theory
- Brooks' graph-coloring theorem and the independence number
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- A short proof of Catlin's extension of Brooks' theorem
- Another bound on the chromatic number of a graph
- Hajos' graph-coloring conjecture: Variations and counterexamples
- A strengthening of Brooks' theorem
- The forest plus stars colouring problem
- The colour theorems of Brooks and Gallai extended
- Spanning trees with pairwise nonadjacent endvertices
- A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem
- Variable degeneracy: Extensions of Brooks' and Gallai's theorems
- On-line list colouring of graphs
- Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
- Three topics in online list coloring
- A different short proof of Brooks' theorem
- Graphs in which every finite path is contained in a circuit
- Bounding the Fractional Chromatic Number of $K_\Delta$-Free Graphs
- A Fractional Analogue of Brooks' Theorem
- On hitting all maximum cliques with an independent set
- A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
- Optimal Vertex Partitions
- The Effective Version of Brooks' Theorem
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Short proofs of classical theorems
- On Brooks' theorem and some related results.
- Colouring graphs when the number of colours is nearly the maximum degree
- Hitting all maximum cliques with a stable set using lopsided independent transversals
- Coloring Claw-Free Graphs with $\Delta-1$ Colors
- Subcubic triangle-free graphs have fractional chromatic number at most 14/5
- New proof of brooks' theorem
- A new proof of Brooks's chromatic number theorem for graphs
- Graph colouring and the probabilistic method
