A bound on the chromatic number of graphs without certain induced subgraphs
From MaRDI portal
Publication:1150627
DOI10.1016/0095-8956(80)90093-3zbMath0457.05032OpenAlexW2019540488MaRDI QIDQ1150627
Publication date: 1980
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(80)90093-3
Related Items (35)
Triangle-free graphs and forbidden subgraphs ⋮ On the existence of two non-neighboring subgraphs in a graph ⋮ Chromatic bounds for the subclasses of \(pK_2\)-free graphs ⋮ On the chromatic number of \(2 K_2\)-free graphs ⋮ On the chromatic number of some \(P_5\)-free graphs ⋮ Maximum induced matchings in graphs ⋮ Vertex coloring of graphs with few obstructions ⋮ Coloring graph classes with no induced fork via perfect divisibility ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices ⋮ Polynomial bounds for chromatic number II: Excluding a star‐forest ⋮ Coloring of some crown-free graphs ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques ⋮ Chromatic bounds for some subclasses of \((P_3\cup P_2)\)-free graphs ⋮ Bounds for the chromatic number of some \(pK_2\)-free graphs ⋮ Locally bounded coverings and factorial properties of graphs ⋮ Coloring of a superclass of \(2K_2\)-free graphs ⋮ Signed Ramsey numbers ⋮ Hitting all maximum stable sets in \(P_5\)-free graphs ⋮ A Generalization of $$\chi $$-Binding Functions ⋮ Near optimal colourability on hereditary graph families ⋮ Colouring of \((P_3 \cup P_2)\)-free graphs ⋮ The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree ⋮ Independence and matching number in graphs with maximum degree 4 ⋮ A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Chromatic bounds for some classes of \(2 K_2\)-free graphs ⋮ On the chromatic number of (P_{5},windmill)-free graphs ⋮ Graphs with no induced \(C_ 4\) and \(2K_ 2\) ⋮ $(2P_2,K_4)$-Free Graphs are 4-Colorable
Cites Work
This page was built for publication: A bound on the chromatic number of graphs without certain induced subgraphs
