On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
From MaRDI portal
Publication:1903716
DOI10.1016/0012-365X(94)00155-XzbMath0837.05095OpenAlexW1529247354MaRDI QIDQ1903716
Henri Thuillier, Vassilis Giakoumakis, Frédéric Maire, Jean-Luc Fouquet
Publication date: 13 May 1996
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(94)00155-x
Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Chromatic number of \(P_5\)-free graphs: Reed's conjecture ⋮ Chromatic bounds for the subclasses of \(pK_2\)-free graphs ⋮ On the chromatic number of \(2 K_2\)-free graphs ⋮ Vizing bound for the chromatic number on some graph classes ⋮ On the chromatic number of some \(P_5\)-free graphs ⋮ Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ Star chromatic bounds ⋮ On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs ⋮ Weighted parameters in \((P_5,\overline {P_5})\)-free graphs ⋮ On graphs with no induced five‐vertex path or paraglider ⋮ 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 ⋮ Divisibility and coloring of some \(P_5\)-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_5\), kite)-free graphs with small cliques ⋮ A Generalization of $$\chi $$-Binding Functions ⋮ Reconfiguration of vertex colouring and forbidden induced subgraphs ⋮ Stability number of bull- and chair-free graphs revisited ⋮ Star coloring of certain graph classes ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ Some results on maximum stable sets in certain \(P_{5}\)-free graphs ⋮ 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 ⋮ GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ On the chromatic number of \((P_{5},K_{2,t})\)-free graphs ⋮ Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs ⋮ On-line graph coloring of \({\mathbb{P}_5}\)-free graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs ⋮ Chromatic bounds for some classes of \(2 K_2\)-free graphs ⋮ On the chromatic number of (P_{5},windmill)-free graphs ⋮ The stable set polytope for some extensions of \(P_4\)-free graphs ⋮ Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs ⋮ On indicated coloring of some classes of graphs ⋮ On minimal imperfect graphs without induced \(P_5\) ⋮ Stability in \(P_5\)- and banner-free graphs ⋮ Stable sets in certain \(P_6\)-free graphs ⋮ Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes ⋮ On the stable set problem in special \(P_{5}\)-free graphs ⋮ Coloring of \((P_5, 4\)-wheel)-free graphs ⋮ Local transformations of graphs preserving independence number
Cites Work
- A new property of critical imperfect graphs and some consequences
- A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Incidence matrices and interval graphs
- On brittle graphs
- Prime Testing for the Split Decomposition of a Graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
