-boundedness and related problems on graphs without long induced paths: a survey
From MaRDI portal
\( \chi \)-boundedness and related problems on graphs without long induced paths: a survey
Cites work
- scientific article; zbMATH DE number 2186978 (Why is no real title available?)
- scientific article; zbMATH DE number 1002021 (Why is no real title available?)
- scientific article; zbMATH DE number 3144148 (Why is no real title available?)
- scientific article; zbMATH DE number 4202279 (Why is no real title available?)
- scientific article; zbMATH DE number 1375569 (Why is no real title available?)
- scientific article; zbMATH DE number 3747156 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 1286500 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 1455118 (Why is no real title available?)
- scientific article; zbMATH DE number 3420800 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- scientific article; zbMATH DE number 3043302 (Why is no real title available?)
- scientific article; zbMATH DE number 3102312 (Why is no real title available?)
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- A Linear Recognition Algorithm for Cographs
- A Note On Reed's Conjecture
- A Note on "The Comparability Graph of a Tree"
- A bound for the chromatic number of \((P_5, \text{gem})\)-free graphs
- A bound on the chromatic number of graphs without certain induced subgraphs
- A characterization of graphs without long induced paths
- A characterization of perfect graphs
- A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
- A new characterization of \(P_{6}\)-free graphs
- A strengthening of Brooks' theorem
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- A survey of -boundedness
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- A tight linear bound to the chromatic number of (P₅, K₁ +(K₁ K₃))-free graphs
- Acyclic and star colorings of cographs
- Acyclic colorings of planar graphs
- Algorithmic graph theory and perfect graphs
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- An optimal χ‐bound for (P6, diamond)‐free graphs
- An upper bound for the chromatic number of line graphs
- Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs
- Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
- Characterization of \(P_{6}\)-free graphs
- Chromatic bounds for some classes of 2 K₂-free graphs
- Chromatic bounds for some subclasses of (P₃ P₂)-free graphs
- Chromatic number of \(P_5\)-free graphs: Reed's conjecture
- Classes of perfect graphs
- Claw-free graphs---a survey
- Claw-free graphs. VI: Colouring
- Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
- Coloring (P₅, kite)-free graphs with small cliques
- Coloring (gem, co‐gem)‐free graphs
- Coloring Claw-Free Graphs with \Delta-1 Colors
- Coloring edges and vertices of graphs without short or long cycles
- Coloring graph classes with no induced fork via perfect divisibility
- Coloring graphs with no induced five‐vertex path or gem
- Coloring graphs without induced \(P_5\) or \(K_5-e\)
- Coloring of \((P_5, 4\)-wheel)-free graphs
- Coloring of some crown-free graphs
- Coloring quasi-line graphs
- Coloring the hypergraph of maximal cliques of a graph with no long path
- Coloring with no 2-colored \(P_4\)'s
- Colouring graphs with no induced six-vertex path or diamond
- Colouring of (P₃ P₂)-free graphs
- Complement reducible graphs
- Constructions of k-critical P₅-free graphs
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Divisibility and coloring of some \(P_5\)-free graphs
- Dominating cliques in \(P_ 5\)-free graphs
- Dominating cliques in graphs
- Dominating subgraphs in graphs with some forbidden structures
- Erdős–Hajnal for graphs with no 5‐hole
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
- Four-coloring \(P_6\)-free graphs
- From \(\chi\)- to \(\chi_p\)-bounded classes
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- Graph Colorings
- Graph Theory and Probability
- Graph theory
- Graphs with No Induced Five‐Vertex Path or Antipath
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Hadwiger's conjecture
- Hadwiger's conjecture
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Hadwiger's conjecture for some hereditary classes of graphs: a survey
- Hitting all maximum cliques with a stable set using lopsided independent transversals
- Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Independence and matching number in graphs with maximum degree 4
- Independent feedback vertex set for P₅-free graphs
- Independent set in P₅-free graphs in polynomial time
- Independent sets and matchings in subcubic graphs
- Induced subgraphs of graphs with large chromatic number. XII. Distant stars
- Induced subgraphs of graphs with large chromatic number. XIII. New brooms
- Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
- Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs
- Linear recognition of pseudo-split graphs
- Linearly \(\chi \)-bounding \((P_6, C_4)\)-free graphs
- Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
- Minimal imperfect graphs: A simple approach
- NP completeness of finding the chromatic index of regular graphs
- Near optimal colourability on hereditary graph families
- Normal hypergraphs and the perfect graph conjecture
- On 3-colorable P₅-free graphs
- On a property of the class of n-colorable graphs
- On algorithms for (P₅, gem)-free graphs
- On an estimate of the chromatic class of a \(p\)-graph
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- On graphs with no induced five‐vertex path or paraglider
- On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- On the chromatic index of multigraphs without large triangles
- On the chromatic number of (P_{5},windmill)-free graphs
- On the chromatic number of (\(P_6\), diamond)-free graphs
- On the chromatic number of \((P_{5},K_{2,t})\)-free graphs
- On the chromatic number of \(2 K_2\)-free graphs
- On the chromatic number of some \(P_5\)-free graphs
- On the complexity of domination number determination in monogenic classes of graphs
- On the coverings of graphs
- On the divisibility of graphs
- On the hardness of approximating minimization problems
- On the hardness of approximating the chromatic number
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- On the structure of (\(P_{5}\),\,gem)-free graphs
- On the structure of (banner, odd hole)-free graphs
- On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
- On-line and first fit colorings of graphs
- On-line coloring \(k\)-colorable graphs
- On-line graph coloring of \({\mathbb{P}_5}\)-free graphs
- Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs
- Paw-free graphs
- Perfect coloring and linearly χ-boundP6-free graphs
- Perfect divisibility and 2‐divisibility
- Perfect divisibility and coloring of some fork-free graphs
- Perfect graphs
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs
- Polynomial bounds for chromatic number. IV: A near-polynomial bound for excluding the five-vertex path
- Polynomial cases for the vertex coloring problem
- Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs
- Radius Three Trees in Graphs with Large Chromatic Number
- Radius two trees specify χ‐bounded classes
- Ramsey-type theorems
- Recognizing Berge graphs
- Reducibility among combinatorial problems
- Separating polynomial \(\chi\)-boundedness from \(\chi\)-boundedness
- Some problems on induced subgraphs
- Some remarks on the theory of graphs
- Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
- Some results on \(k\)-critical \(P_5\)-free graphs
- Square-Free Graphs with No Six-Vertex Induced Path
- Star coloring of certain graph classes
- Star coloring of graphs
- Substitution and \(\chi\)-boundedness
- Sur le coloriage des graphs
- Sur le problème des courbes gauches en topologie.
- The Erdős-Hajnal conjecture for bull-free graphs
- The Erdős-Hajnal conjecture. A survey
- The NP-Completeness of Edge-Coloring
- The Ramsey number R(3, t) has order of magnitude t2/log t
- The chromatic number of \(\{P_5,K_4\}\)-free graphs
- The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
- The four-colour theorem
- The smallest triangle-free 4-chromatic 4-regular graph
- The strong perfect graph theorem
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Triangle-free graphs and forbidden subgraphs
- Triangle-free graphs with no six-vertex induced path
- Two cases of polynomial-time solvability for the coloring problem
- Two complexity results for the vertex coloring problem
- Vertex colouring and forbidden subgraphs -- a survey
- Vizing bound for the chromatic number on some graph classes
- Zero knowledge and the chromatic number
- \((2P_2,K_4)\)-free graphs are 4-colorable
- \(\chi\)-bounds, operations, and chords
- k-critical graphs in P₅-free graphs
- Über eine Eigenschaft der ebenen Komplexe
Cited in
(5)
This page was built for publication: \( \chi \)-boundedness and related problems on graphs without long induced paths: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7028911)
