Graphs of large chromatic number
Summary: The chromatic number has been a fundamental topic of study in graph theory for more than 150 years. Graph coloring has a deep combinatorial theory and, as with many NP-hard problems, is of interest in both mathematics and computer science. An important challenge is to understand graphs with very large chromatic number. The chromatic number tells us something global about the structure of a graph: if \(G\) has small chromatic number then it can be partitioned into a few very simple pieces. But what if \(G\) has large chromatic number? Is there anything that we can say about its local structure? In particular, are there particular substructures that it must contain? In this paper, we will discuss recent progress and open problems in this area. For the entire collection see [Zbl 07816360].
- A Contribution to the Theory of Chromatic Polynomials
- A polynomial invariant for knots via von Neumann algebras
- A short proof of Kneser's conjecture
- A survey of -boundedness
- Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
- Caterpillars in Erdős-Hajnal
- Chromatically optimal rigid graphs
- Coloring, sparseness and girth
- Detecting a long odd hole
- Detecting an Odd Hole
- Every planar map is four colorable. II: Reducibility
- Excluding hooks and their complements
- Finding a Shortest Odd Hole
- Graph minors. XX: Wagner's conjecture
- Graph Theory and Probability
- scientific article; zbMATH DE number 1002021 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3747156 (Why is no real title available?)
- scientific article; zbMATH DE number 3480625 (Why is no real title available?)
- scientific article; zbMATH DE number 3628985 (Why is no real title available?)
- scientific article; zbMATH DE number 1552836 (Why is no real title available?)
- scientific article; zbMATH DE number 3308988 (Why is no real title available?)
- scientific article; zbMATH DE number 970798 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- scientific article; zbMATH DE number 3019031 (Why is no real title available?)
- Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
- Induced subgraphs of graphs with large chromatic number. I. Odd holes
- Induced subgraphs of graphs with large chromatic number. III: Long holes
- Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- Induced subgraphs of graphs with large chromatic number. VI. Banana trees
- Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
- Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
- Induced subgraphs of graphs with large chromatic number. XII. Distant stars
- Induced subgraphs of graphs with large chromatic number. XIII. New brooms
- Induced subtrees in graphs of large chromatic number
- Kneser's conjecture, chromatic number, and homotopy
- On a Coloring Problem.
- On chromatic number of finite set-systems
- On the Chromatic Number of Subgraphs of a Given Graph
- On the complexity of testing for odd holes and induced odd paths
- On the divisibility of graphs
- Pure pairs. I: Trees and linear anticomplete pairs
- Pure pairs. II: Excluding all subdivisions of a graph
- Radius Three Trees in Graphs with Large Chromatic Number
- Radius two trees specify χ‐bounded classes
- Ramanujan graphs
- Ramsey-type theorems
- Ramsey-type theorems with forbidden subgraphs
- Recent developments in graph Ramsey theory
- Recognizing Berge graphs
- Reducibility among combinatorial problems
- Restricted frame graphs and a conjecture of Scott
- String graphs and separators
- Sur le coloriage des graphs
- The chromatic number of \(\{P_5,K_4\}\)-free graphs
- The Erdős-Hajnal conjecture for bull-free graphs
- The Erdős-Hajnal conjecture for paths and antipaths
- The Random-Cluster Model
- The strong perfect graph theorem
- The structure of almost all graphs in a hereditary property
- Triangle-free intersection graphs of line segments with large chromatic number
This page was built for publication: Graphs of large chromatic number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6198641)
