Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
type: Item
instance of: scholarly article
title: Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
zbMATH Open document ID: 1407.05099
author: Ingo Schiermeyer
author: Bert Randerath
published in: Graphs and Combinatorics
publication date: 2019-03-21T00:00:00Z
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 7040455
zbMATH Keywords: chromatic number
zbMATH Keywords: perfect graphs
zbMATH Keywords: \(\chi \)-bounded
zbMATH Keywords: \(\chi \)-binding function
zbMATH Keywords: forbidden induced subgraph
MaRDI profile type: Publication
full work available at URL: s00373-018-1999-0
OpenAlex ID: W2907799240
cites work: Bisimplicial vertices in even-hole-free graphs
cites work: Linear Ramsey numbers
cites work: Dominating cliques in \(P_ 5\)-free graphs
cites work: Colouring of \((P_3 \cup P_2)\)-free graphs
cites work: Graphs with no induced \(C_ 4\) and \(2K_ 2\)
cites work: The Independence Ratio of Regular Graphs
cites work: Graph Classes: A Survey
cites work: Triangle-free graphs and forbidden subgraphs
cites work: On the chromatic number of \((P_{5},K_{2,t})\)-free graphs
cites work: On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs
cites work: On the chromatic number of \(2 K_2\)-free graphs
cites work: On the structure of (pan, even hole)‐free graphs
cites work: Structure and algorithms for (cap, even hole)-free graphs
cites work: Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
cites work: Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs
cites work: Perfect coloring and linearly χ-boundP6-free graphs
cites work: The Erdős-Hajnal conjecture. A survey
cites work: Claw-free graphs. VI: Colouring
cites work: Perfect divisibility and 2‐divisibility
cites work: The strong perfect graph theorem
cites work: \(K_{4}\)-free graphs with no odd holes
cites work: Substitution and \(\chi\)-boundedness
cites work: Graphs with No Induced Five‐Vertex Path or Antipath
cites work: Induced subgraphs of graphs with large chromatic number. III: Long holes
cites work: Induced subgraphs of graphs with large chromatic number. XI. Orientations
cites work: Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
cites work: On the coverings of graphs
cites work: Recognizing claw-free perfect graphs
cites work: Even and odd holes in cap-free graphs
cites work: Graph Theory and Probability
cites work: The chromatic number of \(\{P_5,K_4\}\)-free graphs
cites work: Forbidden Subgraphs and 3-Colorings
cites work: On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
cites work: On the structure of (even hole, kite)-free graphs
cites work: A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
cites work: Coloring the hypergraph of maximal cliques of a graph with no long path
cites work: Q5749319
cites work: Induced subtrees in graphs of large chromatic number
cites work: Independent sets and matchings in subcubic graphs
cites work: On the structure of (banner, odd hole)‐free graphs
cites work: On the divisibility of graphs
cites work: Classes of perfect graphs
cites work: Note on Choudum's “chromatic bounds for a class of graphs”
cites work: Unsolved graph colouring problems
cites work: Vizing bound for the chromatic number on some graph classes
cites work: Square-Free Graphs with No Six-Vertex Induced Path
cites work: Coloring (gem, co‐gem)‐free graphs
cites work: Chromatic bounds for some classes of \(2 K_2\)-free graphs
cites work: On the chromatic number of (\(P_6\), diamond)-free graphs
cites work: On the chromatic index of multigraphs without large triangles
cites work: Radius two trees specify χ‐bounded classes
cites work: Radius Three Trees in Graphs with Large Chromatic Number
cites work: The Ramsey number R(3, t) has order of magnitude t2/log t
cites work: Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
cites work: A characterization of perfect graphs
cites work: Graphs on surfaces
cites work: Graph colouring and the probabilistic method
cites work: Sur le coloriage des graphs
cites work: Paw-free graphs
cites work: Q4484907
cites work: 3-colorability and forbidden subgraphs. I: Characterizing pairs

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Three-colourability and forbidden subgraphs. II: Polynomial algorithms

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Vertex colouring and forbidden subgraphs -- a survey

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: The strong perfect graph conjecture: 40 years of attempts, and its resolution

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Chromatic number of \(P_5\)-free graphs: Reed's conjecture

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: On the chromatic number of (P_{5},windmill)-free graphs

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Q3129824

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Induced subgraphs of graphs with large chromatic number. I. Odd holes

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Some problems on induced subgraphs

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Q3932997

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Alpha-balanced graphs and matrices and GF(3)-representability of matroids

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Graph colorings with local constraints -- a survey

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: Even-hole-free graphs: A survey

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (cites work)
cites work: A bound on the chromatic number of graphs without certain induced subgraphs

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (DOI)
DOI: 10.1007/S00373-018-1999-0

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs
Similarity Score: 0.91211903
Recommender Run: Recommender Run 2

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
Similarity Score: 0.8808656
Recommender Run: Recommender Run 2

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: Forbidden induced subgraphs for bounded \(p\)-intersection number
Similarity Score: 0.8744917
Recommender Run: Recommender Run 2

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
Similarity Score: 0.86322343
Recommender Run: Recommender Run 2

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
Similarity Score: 0.860309
Recommender Run: Recommender Run 2

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: Bounds to the chromatic polynomial of a graph
Similarity Score: 0.85675776
Recommender Run: Recommender Run 2

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials
Similarity Score: 0.8559122
Recommender Run: Recommender Run 2

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: On double bound graphs and forbidden subposets
Similarity Score: 0.85522085
Recommender Run: Recommender Run 2

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: On double bound graphs and forbidden subposets
Similarity Score: 0.85522085
Recommender Run: Recommender Run 2

Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey (Recommended article)
Recommended article: Bounds for the b-chromatic Number of Induced Subgraphs and G − e
Similarity Score: 0.8551622
Recommender Run: Recommender Run 2