Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions

DOI10.1016/j.dam.2022.05.014zbMath1495.05085arXiv2005.02250OpenAlexW4282924791WikidataQ113877200 ScholiaQ113877200MaRDI QIDQ2166229

Maximilian Geißer, Christoph Brause, Ingo Schiermeyer

Publication date: 24 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.02250

zbMATH Keywords

critical graphs\(P_5\)-free graphs\(\chi\)-binding function\(C_4\)-free graphsbanner-free graphsco-banner-free graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items

A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs ⋮ Vertex-critical \((P_5, \mathrm{chair})\)-free graphs ⋮ Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs ⋮ Divisibility and coloring of some \(P_5\)-free graphs ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• Polynomial cases for the vertex coloring problem
• The strong perfect graph theorem
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• Paw-free graphs
• A bound on the chromatic number of graphs without certain induced subgraphs
• On the chromatic number of \(2 K_2\)-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Normal hypergraphs and the perfect graph conjecture
• On a property of the class of n-colorable graphs
• Graph Theory and Probability
• Perfect coloring and linearly χ-boundP6-free graphs
• The Independence Ratio of Regular Graphs
• On the structure of (banner, odd hole)‐free graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• A survey of χ‐boundedness
• $(2P_2,K_4)$-Free Graphs are 4-Colorable
• Perfect divisibility and 2‐divisibility
• Static frequency assignment in cellular networks
• On graphs with no induced five‐vertex path or paraglider
• Coloring graphs with no induced five‐vertex path or gem