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
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references