Graphs of large chromatic number (Q6198641)
From MaRDI portal
scientific article; zbMATH DE number 7821707
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphs of large chromatic number |
scientific article; zbMATH DE number 7821707 |
Statements
Graphs of large chromatic number (English)
0 references
20 March 2024
0 references
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].
0 references
graph coloring
0 references
induced subgraphs
0 references
\(\chi\)-boundedness
0 references
Erdős-Hajnal conjecture
0 references
0 references