A strengthening of Brooks' theorem
From MaRDI portal
Publication:1306303
DOI10.1006/JCTB.1998.1891zbMATH Open0935.05045OpenAlexW2011731192MaRDI QIDQ1306303FDOQ1306303
Publication date: 20 December 1999
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1998.1891
Recommendations
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)
Cites Work
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A bound on the strong chromatic index of a graph
- Weighted sums of certain dependent random variables
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A bound on the total chromatic number
- Title not available (Why is that?)
Cited In (41)
- The list version of the Borodin-Kostochka conjecture for graphs with large maximum degree
- A note on coloring vertex-transitive graphs
- Graphs with $\chi=\Delta$ Have Big Cliques
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
- Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors
- Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
- On the Grundy Number of a Graph
- Title not available (Why is that?)
- A note on \(\Delta\)-critical graphs
- Borodin-Kostochka conjecture holds for odd-hole-free graphs
- Algorithmic bounds for the chromatic number†
- Coloring hammer-free graphs with \(\Delta - 1\) colors
- Large cliques in graphs with high chromatic number
- The distance coloring of graphs
- A reconfigurations analogue of Brooks' theorem and its consequences
- Convex hull of face vectors of colored complexes
- An NC algorithm for Brooks' theorem
- On graphs with linear Ramsey numbers
- Ramsey-nice families of graphs
- On the connection between chromatic number, maximal clique and minimal degree of a graph
- Chromatic numbers of layered graphs with a bounded maximal clique
- The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs
- Partitioning of a graph into induced subgraphs not containing prescribed cliques
- Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
- Coloring Graphs with Dense Neighborhoods
- Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
- Joints in graphs
- Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
- Special issue in honour of Landon Rabern
- Borodin-Kostochka's conjecture on \(\{P_2 \cup P_3, C_4\}\)-free graphs
- A strengthening of the Assmus-Mattson theorem
- (\(\Delta-k\))-critical graphs
- Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
- List-Coloring Claw-Free Graphs with $\Delta-1$ Colors
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Asymptotically optimal frugal colouring
- Dynamic proper colorings of a graph
- Bounds and monotonicity of critical set parameters of colourings
- Bounded \(VC\)-dimension implies the Schur-Erdős conjecture
- Brooks' Theorem and Beyond
- On the Grundy and \(b\)-chromatic numbers of a graph
This page was built for publication: A strengthening of Brooks' theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306303)
