Paw-free graphs

DOI10.1016/0020-0190(88)90143-3zbMATH Open0654.05063OpenAlexW94262720MaRDI QIDQ1108293FDOQ1108293

Stephan Olariu

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90143-3

Recommendations

• On the quasi-locally paw-free graphs
• Claw-free graphs. IV: Decomposition theorem
• Recognizing claw-free perfect graphs
• Claw-free graphs. V. Global structure
• The structure of claw-free graphs

zbMATH Keywords

algorithmsdecomposition theoremgraph decompositionperfect graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Perfect graphs (05C17)

Cites Work

• A Linear Recognition Algorithm for Cographs
• Title not available (Why is that?)
• Topics on perfect graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recognizing claw-free perfect graphs
• A new property of critical imperfect graphs and some consequences
• Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs)

Cited In (92)

• Regular languages and partial commutations
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• Disconnected cuts in claw-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs
• On perfectness of sums of graphs
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
• Two forbidden induced subgraphs and well-quasi-ordering
• Colouring vertices of triangle-free graphs without forests
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• Perfectly colorable graphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• Forbidden pairs and the existence of a dominating cycle
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs
• On the relation of strong triadic closure and cluster deletion
• The descriptive complexity of subgraph isomorphism without numerics
• 3-colorability and forbidden subgraphs. I: Characterizing pairs
• Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Reducing the chromatic number by vertex or edge deletions
• Claw-free graphs---a survey
• Two classes of perfect graphs
• Characterizing forbidden pairs for relative length of longest paths and cycles
• Finding and counting small induced subgraphs efficiently
• Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
• Chromatic symmetric functions and \(H\)-free graphs
• On the complexity of cd-coloring of graphs
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Title not available (Why is that?)
• Chair-free Berge graphs are perfect
• Detecting and Counting Small Pattern Graphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Duality for semiantichains and unichain coverings in products of special posets
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Polynomial kernels for paw-free edge modification problems
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time
• Independent sets in \((P_4+P_4\),triangle)-free graphs
• Stable sets in certain \(P_6\)-free graphs
• The chromatic discrepancy of graphs
• On indicated coloring of graphs
• Indicated coloring of the Mycielskian of some families of graphs
• Classes of perfect graphs
• Dominating cycles and forbidden pairs containing \(P_5\)
• Detecting and enumerating small induced subgraphs in \(c\)-closed graphs
• Chromatic bounds for some subclasses of \((P_3\cup P_2)\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• On the quasi-locally paw-free graphs
• Partial characterizations of circular-arc graphs
• Title not available (Why is that?)
• Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
• \(k\)-critical graphs in \(P_5\)-free graphs
• Square-free perfect graphs.
• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time
• Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
• Graph classes with linear Ramsey numbers
• The complexity of partitioning into disjoint cliques and a triangle-free graph
• A note on sparseness conditions on chordless vertices of cycles
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
• Excluding induced subdivisions of the bull and related graphs
• Graphs with few trivial characteristic ideals
• Characterizing the difference between graph classes defined by forbidden pairs including the claw
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Cutting a tree with subgraph complementation is hard, except for some small trees
• On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
• Clique‐width: Harnessing the power of atoms
• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• Title not available (Why is that?)
• On indicated coloring of lexicographic product of graphs
• Near optimal colourability on hereditary graph families
• Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
• Reconfiguration of vertex colouring and forbidden induced subgraphs
• The chromatic number of (\(P_5\), HVN)-free graphs
• Sandwiches missing two ingredients of order four
• Linear χ -binding functions for some classes of ( P ₃ ∪ P ₂ )-free graphs
• Recoloring some hereditary graph classes
• The complement of the Djoković-Winkler relation
• Finding and counting small induced subgraphs efficiently
• Ramsey numbers and graph parameters
• Clique-perfectness and balancedness of some graph classes
• Forbidden subgraphs for graphs with (near) perfect matching to be hamiltonian
• A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques
• Coloring of a superclass of \(2K_2\)-free graphs

This page was built for publication: Paw-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108293)