Paw-free graphs
From MaRDI portal
The graph with vertices \(a, b, c, d\) and edges \(ab, bc, bd, cd\) will be referred to as the paw. A graph \(G\) is called paw-free if it contains no induced subgraph isomorphic to the paw. We characterize paw-free graphs and give polynomial-time algorithms for recognizing them as well as algorithms for finding the largest clique and the largest stable set in a paw-free graph.
Recommendations
Cites work
- A Linear Recognition Algorithm for Cographs
- A new property of critical imperfect graphs and some consequences
- Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs)
- scientific article; zbMATH DE number 3889565 (Why is no real title available?)
- scientific article; zbMATH DE number 3889583 (Why is no real title available?)
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- Recognizing claw-free perfect graphs
- Topics on perfect graphs
Cited in
(only showing first 100 items - show all)- Duality for semiantichains and unichain coverings in products of special posets
- Two classes of perfect graphs
- On perfectness of sums of graphs
- Stable sets in certain \(P_6\)-free graphs
- Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
- Claw-free graphs---a survey
- Chair-free Berge graphs are perfect
- 3-colorability and forbidden subgraphs. I: Characterizing pairs
- Square-free perfect graphs.
- Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- On the quasi-locally paw-free graphs
- Perfectly colorable graphs
- On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs
- Chromatic symmetric functions and \(H\)-free graphs
- Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time
- Detecting and enumerating small induced subgraphs in c-closed graphs
- Independent sets in \((P_4+P_4\),triangle)-free graphs
- Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
- Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs
- Characterizing forbidden pairs for relative length of longest paths and cycles
- On indicated coloring of lexicographic product of graphs
- Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
- On the complexity of cd-coloring of graphs
- Disconnected cuts in claw-free graphs
- Graphs with few trivial characteristic ideals
- The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
- Two forbidden induced subgraphs and well-quasi-ordering
- Characterizing the difference between graph classes defined by forbidden pairs including the claw
- Sandwiches missing two ingredients of order four
- The chromatic discrepancy of graphs
- Reducing the chromatic number by vertex or edge deletions
- Classes of perfect 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
- Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
- Graph classes with linear Ramsey numbers
- Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- Excluding induced subdivisions of the bull and related graphs
- Clique-perfectness and balancedness of some graph classes
- Clique-width of graph classes defined by two forbidden induced subgraphs
- Finding and counting small induced subgraphs efficiently
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- On the first-order complexity of induced subgraph isomorphism
- Dominating cycles and forbidden pairs containing \(P_5\)
- Partial characterizations of circular-arc graphs
- A note on sparseness conditions on chordless vertices of cycles
- Regular languages and partial commutations
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Tensor network complexity of multilinear maps
- Counting connected subgraphs with maximum-degree-aware sieving
- Forbidden subgraphs for graphs with (near) perfect matching to be Hamiltonian
- The complexity of partitioning into disjoint cliques and a triangle-free graph
- Detecting and counting small pattern graphs
- scientific article; zbMATH DE number 7651161 (Why is no real title available?)
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- \(k\)-critical graphs in \(P_5\)-free graphs
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Polynomial kernels for paw-free edge modification problems
- k-critical graphs in P₅-free graphs
- Rare siblings speed-up deterministic detection and counting of small pattern graphs
- Clique‐width: Harnessing the power of atoms
- scientific article; zbMATH DE number 7764101 (Why is no real title available?)
- Chromatic bounds for some subclasses of (P₃ P₂)-free graphs
- Ramsey numbers and graph parameters
- Finding and counting small induced subgraphs efficiently
- Coloring of a superclass of 2K₂-free graphs
- Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
- Cutting a tree with subgraph complementation is hard, except for some small trees
- Indicated coloring of the Mycielskian of some families of graphs
- On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
- Near optimal colourability on hereditary graph families
- Reconfiguration of vertex colouring and forbidden induced subgraphs
- Cutting a tree with subgraph complementation is hard, except for some small trees
- The chromatic number of (\(P_5\), HVN)-free graphs
- Linear χ -binding functions for some classes of ( P 3 ∪ P 2 )-free graphs
- Recoloring some hereditary graph classes
- The complement of the Djoković-Winkler relation
- On near optimal colorable graphs
- Secure domination in P₅-free graphs
- Atoms versus avoiding simplicial vertices
- Longest path transversals in claw-free and P₅-free graphs
- The complexity of diameter on H-free graphs
- Primitive, edge-short, isometric, and pantochordal cycles
- Structure of (bull, diamond)-free graphs and its applications
- Near optimal colourability on (H, K_n - e)-free graphs
- -boundedness and related problems on graphs without long induced paths: a survey
- Switching classes: characterization and computation
- Treewidth versus clique number. V: Further connections with tree-independence number
- On the chromatic number of a superclass of 2 K₂-free graphs
- Polynomial kernel and incompressibility for prison-free edge deletion and completion
- Graphs with two trivial distance ideals over the ring of polynomials with integer coefficients
- Linear colorings of 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)
