Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
From MaRDI portal
Publication:1733849
DOI10.1007/s00373-018-1999-0zbMath1407.05099OpenAlexW2907799240MaRDI QIDQ1733849
Ingo Schiermeyer, Bert Randerath
Publication date: 21 March 2019
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00373-018-1999-0
Related Items (32)
Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4 ⋮ Chromatic bounds for the subclasses of \(pK_2\)-free graphs ⋮ Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs ⋮ On the chromatic number of some \(P_5\)-free graphs ⋮ Coloring graph classes with no induced fork via perfect divisibility ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices ⋮ On graphs with no induced five‐vertex path or paraglider ⋮ Polynomial bounds for chromatic number II: Excluding a star‐forest ⋮ Polynomial bounds for chromatic number. III. Excluding a double star ⋮ Coloring of some crown-free graphs ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ Polynomial bounds for chromatic number VII. Disjoint holes ⋮ On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques ⋮ Coloring graphs without induced \(P_5\) or \(K_5-e\) ⋮ Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs ⋮ Bounds for the chromatic number of some \(pK_2\)-free graphs ⋮ On the chromatic number of (P5,dart)-free graphs ⋮ Coloring of a superclass of \(2K_2\)-free graphs ⋮ Coloring graphs with no induced five‐vertex path or gem ⋮ Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs ⋮ Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors ⋮ Polynomial bounds for chromatic number. V: Excluding a tree of radius two and a complete multipartite graph ⋮ Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs ⋮ Coloring (\(P_5\), kite)-free graphs with small cliques ⋮ Near optimal colourability on hereditary graph families ⋮ Polynomial bounds for chromatic number VI. Adding a four-vertex path ⋮ A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs ⋮ Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs ⋮ A better upper bound on the chromatic number of (cap, even-hole)-free graphs ⋮ Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs ⋮ Coloring of \((P_5, 4\)-wheel)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Chromatic number of \(P_5\)-free graphs: Reed's conjecture
- Induced subgraphs of graphs with large chromatic number. I. Odd holes
- Independent sets and matchings in subcubic graphs
- Substitution and \(\chi\)-boundedness
- On the chromatic number of \((P_{5},K_{2,t})\)-free graphs
- Claw-free graphs. VI: Colouring
- Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
- Induced subgraphs of graphs with large chromatic number. III: Long holes
- On the chromatic index of multigraphs without large triangles
- The strong perfect graph theorem
- Bisimplicial vertices in even-hole-free graphs
- \(K_{4}\)-free graphs with no odd holes
- Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Paw-free graphs
- Recognizing claw-free perfect graphs
- On the coverings of graphs
- A bound on the chromatic number of graphs without certain induced subgraphs
- Induced subtrees in graphs of large chromatic number
- Alpha-balanced graphs and matrices and GF(3)-representability of matroids
- Dominating cliques in \(P_ 5\)-free graphs
- Coloring the hypergraph of maximal cliques of a graph with no long path
- 3-colorability and forbidden subgraphs. I: Characterizing pairs
- Triangle-free graphs and forbidden subgraphs
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Induced subgraphs of graphs with large chromatic number. XI. Orientations
- On the chromatic number of \(2 K_2\)-free graphs
- Linear Ramsey numbers
- Structure and algorithms for (cap, even hole)-free graphs
- Some problems on induced subgraphs
- Colouring of \((P_3 \cup P_2)\)-free graphs
- On the structure of (even hole, kite)-free graphs
- Chromatic bounds for some classes of \(2 K_2\)-free graphs
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Vertex colouring and forbidden subgraphs -- a survey
- On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
- The chromatic number of \(\{P_5,K_4\}\)-free graphs
- On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs
- 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
- On the chromatic number of (\(P_6\), diamond)-free graphs
- Classes of perfect graphs
- A characterization of perfect graphs
- Vizing bound for the chromatic number on some graph classes
- The Erdös-Hajnal Conjecture-A Survey
- Forbidden Subgraphs and 3-Colorings
- Graphs with No Induced Five‐Vertex Path or Antipath
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Graph Theory and Probability
- Perfect coloring and linearly χ-boundP6-free graphs
- Note on Choudum's “chromatic bounds for a class of graphs”
- The Independence Ratio of Regular Graphs
- Graph colorings with local constraints -- a survey
- Even and odd holes in cap-free graphs
- Graph Classes: A Survey
- Radius two trees specify χ‐bounded classes
- On the structure of (pan, even hole)‐free graphs
- Coloring (gem, co‐gem)‐free graphs
- On the structure of (banner, odd hole)‐free graphs
- Radius Three Trees in Graphs with Large Chromatic Number
- On the chromatic number of (P_{5},windmill)-free graphs
- The Ramsey number R(3, t) has order of magnitude t2/log t
- Even-hole-free graphs: A survey
- Square-Free Graphs with No Six-Vertex Induced Path
- Perfect divisibility and 2‐divisibility
- Sur le coloriage des graphs
- Graph colouring and the probabilistic method
- On the divisibility of graphs
This page was built for publication: Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
