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
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
