Paw-free graphs
From MaRDI portal
Publication:1108293
DOI10.1016/0020-0190(88)90143-3zbMath0654.05063OpenAlexW94262720MaRDI QIDQ1108293
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
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Related Items (87)
Perfect graphs with no \(P_ 5\) and no \(K_ 5\) ⋮ Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ Finding and counting small induced subgraphs efficiently ⋮ 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 ⋮ Excluding Induced Subdivisions of the Bull and Related Graphs ⋮ Claw-free graphs---a survey ⋮ Dominating cycles and forbidden pairs containing \(P_5\) ⋮ On indicated coloring of lexicographic product of graphs ⋮ Two classes of perfect graphs ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Clique-perfectness and balancedness of some graph classes ⋮ Graph classes with linear Ramsey numbers ⋮ Chair-free Berge graphs are perfect ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ A note on sparseness conditions on chordless vertices of cycles ⋮ On the complexity of cd-coloring of graphs ⋮ Reducing the chromatic number by vertex or edge deletions ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Regular languages and partial commutations ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ Disconnected cuts in claw-free graphs ⋮ Clique‐width: Harnessing the power of atoms ⋮ Chromatic bounds for some subclasses of \((P_3\cup P_2)\)-free graphs ⋮ On indicated coloring of graphs ⋮ Ramsey numbers and graph parameters ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Coloring of a superclass of \(2K_2\)-free graphs ⋮ Strengthening Brooks' chromatic bound on \(P_6\)-free graphs ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Unnamed Item ⋮ Indicated coloring of the Mycielskian of some families of graphs ⋮ Perfectly colorable 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 ⋮ Classes of perfect graphs ⋮ Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Unnamed Item ⋮ 3-colorability and forbidden subgraphs. I: Characterizing pairs ⋮ A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques ⋮ Square-free perfect graphs. ⋮ Finding and counting small induced subgraphs efficiently ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Graphs with few trivial characteristic ideals ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ A fast deterministic detection of small pattern graphs in graphs without large cliques ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ The complexity of partitioning into disjoint cliques and a triangle-free graph ⋮ 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 ⋮ Forbidden subgraphs for graphs with (near) perfect matching to be hamiltonian ⋮ Unnamed Item ⋮ On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs ⋮ Chromatic symmetric functions and \(H\)-free graphs ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Detecting and Counting Small Pattern Graphs ⋮ Two forbidden induced subgraphs and well-quasi-ordering ⋮ On the relation of strong triadic closure and cluster deletion ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Characterizing the difference between graph classes defined by forbidden pairs including the claw ⋮ Sandwiches missing two ingredients of order four ⋮ Forbidden pairs and the existence of a dominating cycle ⋮ \(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 ⋮ 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 ⋮ Polynomial kernels for paw-free edge modification problems ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ Duality for semiantichains and unichain coverings in products of special posets ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ On the quasi-locally paw-free graphs ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs ⋮ Colouring vertices of triangle-free graphs without forests ⋮ Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions ⋮ Partial characterizations of circular-arc graphs ⋮ On perfectness of sums of graphs ⋮ Stable sets in certain \(P_6\)-free graphs ⋮ The chromatic discrepancy of graphs
Cites Work
This page was built for publication: Paw-free graphs
