Complement reducible graphs

DOI10.1016/0166-218X(81)90013-5zbMath0463.05057OpenAlexW2028775537WikidataQ55951980 ScholiaQ55951980MaRDI QIDQ1153105

L. Stewart Burlingham, H. Lerchs, Derek Gordon Corneil

Publication date: 1981

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(81)90013-5

zbMATH Keywords

cographs comparability graphs dacey graphs

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75)

Related Items

Clique-width of path powers, Characterizations for co-graphs defined by restricted NLC-width or clique-width operations, Detour trees, Distance-hereditary graphs, Linearity is strictly more powerful than contiguity for encoding graphs, On the terminal connection problem, On some complexity properties of N-free posets and posets with bounded decomposition diameter, The micro-world of cographs, Thinness of product graphs, Cyclability in graph classes, Finding pattern matchings for permutations, Pattern matching for permutations, Recognizing cographs and threshold graphs through a classification of their edges, Generating and enumerating digitally convex sets of trees, A new characterization of \(P_k\)-free graphs, Edge-colouring of joins of regular graphs. I, Inapproximability of the lid-chromatic number, Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs, On the chromatic index of cographs and join graphs, Tent and a subclass of \(P_{5}\)-free graphs, Locally perfect graphs, Dominating sets in social network graphs, Graph isomorphism for graph classes characterized by two forbidden induced subgraphs, Linear time algorithms for NP-hard problems restricted to partial k- trees, Strong tree-cographs are Birkhoff graphs, Constructably Laplacian integral graphs, Laplacian integral graphs in \(S(a, b)\), On bipartite graphs with weak density of some subgraphs, Partitions of graphs into cographs, Regular languages and partial commutations, On CIS circulants, On the \(b\)-coloring of \(P_{4}\)-tidy graphs, Enumeration of point-determining graphs, On indicated coloring of graphs, Edge search number of cographs, On parallel recognition of cographs, Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques, Algorithmic aspects of switch cographs, Some spectral properties of cographs, Four-cycled graphs with topological applications, Complexity of independent set reconfigurability problems, Primitivity is hereditary for 2-structures, Hamiltonian properties of locally connected graphs with bounded vertex degree, Acyclic and star colorings of cographs, Parallel recognition of complement reducible graphs and cotree construction, Subgraph isomorphism in graph classes, A survey of the algorithmic aspects of modular decomposition, On the complexity of dynamic programming for sequencing problems with precedence constraints, Clique-width with an inactive label, Permutation graphs: Connected domination and Steiner trees, On the rank of a cograph, A simple linear-time recognition algorithm for weakly quasi-threshold graphs, Path-bicolorable graphs, On the geodeticity of the contour of a graph, The maximum edit distance from hereditary graph properties, Pseudo-median graphs: Decomposition via amalgamation and Cartesian multiplication, A tree representation for \(P_ 4\)-sparse graphs, Characterization and complexity of uniformly nonprimitive labeled 2-structures, A linear-time recognition algorithm for \(P_{4}\)-reducible graphs, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, An improvement on the complexity of factoring read-once Boolean functions, Comparing the metric and strong dimensions of graphs, Finding Hamiltonian circuits in quasi-adjoint graphs, Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm, An O(\(n\)) time algorithm for maximum matching on cographs, Automorphism groups of graphs with forbidden subgraphs, Computing residual connectedness reliability for restricted networks, \(P_ 4\)-trees and substitution decomposition, \(1\)-perfectly orientable graphs and graph products, Recent developments on graphs of bounded clique-width, First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs, A forbidden subgraph characterization of line-polar bipartite graphs, On estimating the number of order ideals in partial orders, with some applications, Characterizing and computing minimal cograph completions, On Hadamard diagonalizable graphs, Maximum independent sets in subclasses of \(P_{5}\)-free graphs, Completion of Laplacian integral graphs via edge addition, On the structure of strong 3-quasi-transitive digraphs, On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions, Clique-width of graphs defined by one-vertex extensions, On \(P_4\)-transversals of chordal graphs, The stable set polytope for some extensions of \(P_4\)-free graphs, Representation of graphs by OBDDs, Structure and stability number of chair-, co-P- and gem-free graphs revisited, Dominating sequences in graphs, Characterizations of cographs as intersection graphs of paths on a grid, Efficient algorithms for network localization using cores of underlying graphs, On the OBDD size for graphs of bounded tree- and clique-width, The graph sandwich problem for \(P_4\)-sparse graphs, Algorithmic aspects of a general modular decomposition theory, Some optimization problems on weak-bisplit graphs, Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes, The possible cardinalities of global secure sets in cographs, Toughness and prism-Hamiltonicity of \(P_4\)-free graphs, On the b-coloring of cographs and \(P_{4}\)-sparse graphs, A note on a conjecture by Gavril on clique separable graphs, Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey, Clustering and domination in perfect graphs, Orientations of graphs in kernel theory, On algorithms for (\(P_5\), gem)-free graphs, One-three join: a graph operation and its consequences, Symmetric linear spaces of graphs, A characterization and hereditary properties for partition graphs, Handle-rewriting hypergraph grammars, A faster parallel connectivity algorithm on cographs, Linearity Is Strictly More Powerful Than Contiguity for Encoding Graphs, On the complexity of reconstructing H-free graphs from their Star Systems, When every k-cycle has at least f(k) chords, Recognizing well covered graphs of families with special \(P _{4}\)-components, Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model, A Brooks‐Type Theorem for the Bichromatic Number, On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions, Unnamed Item, P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs, Clique-perfectness and balancedness of some graph classes, Complete characterization of incorrect orthology assignments in best match graphs, Graph classes with linear Ramsey numbers, Perfect graphs for domination games, 4-coloring \((P_6, \text{bull})\)-free graphs, Perfect Italian domination in cographs, Steiner trees for hereditary graph classes: a treewidth perspective, Families of integral cographs within a triangular array, Minimal asymmetric graphs, On the thinness and proper thinness of a graph, Contraction Blockers for Graphs with Forbidden Induced Paths, Complete edge-colored permutation graphs, Minimal obstructions to \(( s , 1 )\)-polarity in cographs, Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs, Secure domination in cographs, On estimation of the number of graphs in some hereditary classes, Integral cographs, Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees, The restrained double Roman domination in graphs, Strongly Even-Cycle Decomposable Graphs, Characterizing and Computing Minimal Cograph Completions, Mixed Search Number of Permutation Graphs, Simple permutations and algebraic generating functions, Maximizing the strong triadic closure in split graphs and proper interval graphs, Defective Ramsey numbers and defective cocolorings in some subclasses of perfect graphs, Fixed-parameter algorithms for the cocoloring problem, 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles, Nordhaus-Gaddum bounds for locating domination, Solutions for subset sum problems with special digraph constraints, On the complexity of the black-and-white coloring problem on some classes of perfect graphs, Computing square roots of trivially perfect and threshold graphs, Maximization coloring problems on graphs with few \(P_4\), Graphs whose complement and square are isomorphic, How to compute digraph width measures on directed co-graphs, Counting subset repairs with functional dependencies, \((k,l)\)-colourings and Ferrers diagram representations of cographs, Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract), Finding a minimum path cover of a distance-hereditary graph in polynomial time, The harmonious coloring problem is NP-complete for interval and permutation graphs, Shortest Paths between Shortest Paths and Independent Sets, Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee, Efficient computation of the oriented chromatic number of recursively defined digraphs, Edge-colouring of regular graphs of large degree, Coherent network partitions: characterizations with cographs and prime graphs, Some new classes of open distance-pattern uniform graphs, Unnamed Item, On Some Properties of the Struction of a Graph, Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees, Fully dynamic recognition algorithm and certificate for directed cographs, On the complexity of the independent set problem in triangle graphs, Partitioning a graph into convex sets, Finitely forcible graphons, Characterization of general position sets and its applications to cographs and bipartite graphs, A note on the bichromatic numbers of graphs, A note on a conjecture for the distance Laplacian matrix, Complexity of modification problems for reciprocal best match graphs, Reciprocal best match graphs, Online coloring a token graph, Best match graphs and reconciliation of gene trees with species trees, Defining and identifying cograph communities in complex networks, A multivariate analysis of the strict terminal connection problem, Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width, On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs, Alternative characterizations of Fitch's xenology relation, Linear-time algorithm for the matched-domination problem in cographs, Cographs: eigenvalues and Dilworth number, Unsmoothable group actions on compact one-manifolds, Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees, Laplacian integrality in \(P_4\)-sparse and \(P_4\)-extendible graphs, Self-spanner graphs, Efficient parallel recognition of cographs, Partitioning cographs into cliques and stable sets, Digraphs of Bounded Width, Perfect Roman domination in graphs, On the double Roman domination of graphs, On the spectrum and number of convex sets in graphs, On the relationship between NLC-width and linear NLC-width, Extending the MAX algorithm for maximum independent set, New sufficient conditions for \(\alpha\)-redundant vertices, The bi-join decomposition, Read-Once Functions Revisited and the Readability Number of a Boolean Function, Independent Domination in Triangle Graphs, On maximum independent set of categorical product and ultimate categorical ratios of graphs, Partitioning a graph into disjoint cliques and a triangle-free graph, Knocking out \(P_k\)-free graphs, Unnamed Item, Binomial edge ideals of cographs, A polynomial time algorithm for geodetic hull number for complementary prisms, On the Complexity of Finding a Potential Community, A note on strong perfectness of graphs, Linear-sized independent sets in random cographs and increasing subsequences in separable permutations, The pathwidth and treewidth of cographs, Parallel algorithm for cograph recognition with applications, Hierarchical and modularly-minimal vertex colorings, Unnamed Item, Unnamed Item, AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS, Edge Search Number of Cographs in Linear Time, The Smallest Classes of Binary and Ternary Matroids Closed under Direct Sums and Complements, Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded, On the computational difficulty of the terminal connection problem, Edge clique covers in graphs with independence number two, Almost controllable graphs and beyond, Graphon convergence of random cographs, Random cographs: Brownian graphon limit and asymptotic degree distribution, Representing formulas of propositional logic by cographs, permutations and tables, Classification of non-solvable groups whose power graph is a cograph, Optimal parallel colouring algorithms for totally decomposable graphs, Reducing graph parameters by contractions and deletions, On the isomorphism of graphs with few P4s, Efficient parallel modular decomposition (extended abstract), The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs, Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints, Enumerating Independent Linear Inferences, A System of Interaction and Structure III: The Complexity of BV and Pomset Logic, Asteroidal triple-free graphs, Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes, Stability, vertex stability, and unfrozenness for special graph classes, Computing and listing avoidable vertices and paths, Laplacian eigenvalues of equivalent cographs, Cutting a tree with subgraph complementation is hard, except for some small trees, Probe Ptolemaic Graphs, Partitioning \(P_4\)-tidy graphs into a stable set and a forest, New results on complementarity spectra of connected graphs, Laplacian spectra of cographs: a twin reduction perspective, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, Cographs and 1-sums, Directed path graph isomorphism, Algorithms and complexity of sandwich problems in graphs (extended abstract), Computing well-covered vector spaces of graphs using modular decomposition, \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs, Automata-based Representations for Infinite Graphs, Locating Eigenvalues of Symmetric Matrices - A Survey, Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs, Cograph editing: Merging modules is equivalent to editing P_4s, On König graphs with respect to P4, Unnamed Item, Unnamed Item, Unnamed Item, Precoloring Extension III: Classes of Perfect Graphs, GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH, -cospectrality and -energy in cographs, Acyclic polynomials of graphs, Polar cographs, Polar cographs, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Towards Hilbert's 24th Problem: Combinatorial Proof Invariants, Pattern matching for permutations, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Split non-threshold Laplacian integral graphs, Strong triadic closure in cographs and graphs of low maximum degree, Faster and enhanced inclusion-minimal cograph completion, On graphs whose smallest distance (signless Laplacian) eigenvalue has large multiplicity, When can graph hyperbolicity be computed in linear time?, Graph transformations preserving the stability number, A short note on undirected Fitch graphs, Enumeration Schemes for Restricted Permutations, Secure total domination in chain graphs and cographs, A semi-strong perfect digraph theorem, Graph isomorphism restricted by lists, Scattered Classes of Graphs, On the Complexity of Reconstructing H-free Graphs from Their Star Systems, Disjoint paths and connected subgraphs for \(H\)-free graphs, Disjoint paths and connected subgraphs for \(H\)-free graphs, Computing subset transversals in \(H\)-free graphs, Spectral properties of cographs andP₅-free graphs, Parameterized inapproximability of independent set in \(H\)-free graphs, On the Mean Connected Induced Subgraph Order of Cographs, Counting Perfect Matchings and the Switch Chain, Unnamed Item, Unnamed Item, Unnamed Item, Partial characterizations of circular-arc graphs, Path-Bicolorable Graphs, On zero forcing number of graphs and their complements, Crossing Layout in Non-planar Graph Drawings, ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S, NLC₂-DECOMPOSITION IN POLYNOMIAL TIME, A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join of Regular Graphs, Efficient Local Representations of Graphs, On perfect and quasiperfect dominations in graphs, Aα and Lα-spectral properties of spider graphs, A theorem on permutation graphs with applications, The knapsack problem with special neighbor constraints, PLA folding in special graph classes, Computing directed Steiner path covers, Relationships between algebraic connectivity and vertex connectivity, Eigenvalue location in graphs of small clique-width, A characterization of claw-free CIS graphs and new results on the order of CIS graphs, PSPACE-hardness of two graph coloring games, Linear-time minimal cograph editing, Efficient parallel recognition algorithms of cographs and distance hereditary graphs, Isomorphism of chordal (6, 3) graphs, Complexity of list coloring problems with a fixed total number of colors, Fixed-parameter tractability of graph modification problems for hereditary properties, Linear time optimization algorithms for \(P_ 4\)-sparse graphs, Bi-complement reducible graphs, Matroids arisen from matrogenic graphs, On semi-\(P_ 4\)-sparse graphs, Scattering number and modular decomposition, An optimal path cover algorithm for cographs, Generalized coloring for tree-like graphs, The monadic second-order logic of graphs. X: Linear orderings, On the rank of the distance matrix of graphs, Perfect matching cuts partitioning a graph into complementary subgraphs, Homomorphically full graphs, From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, Multiplicity of eigenvalues of cographs, Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions, A fast parallel algorithm to recognize P4-sparse graphs, HAMILTONian circuits in chordal bipartite graphs, Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, Quasi-threshold graphs, Logical description of context-free graph languages, Approximating weighted neighborhood independent sets, PSPACE-completeness of two graph coloring games, On some graph classes related to perfect graphs: a survey, On the structure of graphs with few \(P_4\)s, Locally identifying coloring of graphs with few P4s, Multiplicities of distance Laplacian eigenvalues and forbidden subgraphs, Orthology relations, symbolic ultrametrics, and cographs, A time-optimal solution for the path cover problem on cographs., Cograph generation with linear delay, On variations of \(P_{4}\)-sparse graphs, Subgraph trees in graph theory, Embeddability between right-angled Artin groups.., Stability number of bull- and chair-free graphs revisited, On the structure and stability number of \(P_{5}\)- and co-chair-free graphs, Solving problems on graphs of high rank-width, The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs, On the vertex ranking problem for trapezoid, circular-arc and other graphs, Recognition and isomorphism of tree-like \(P_4\)-connected graphs, A fully dynamic algorithm for modular decomposition and recognition of cographs., (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization., Induced saturation of graphs, The secure domination problem in cographs, Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs, Finding a potential community in networks, Coupon coloring of cographs, On the chromatic index of join graphs and triangle-free graphs with large maximum degree, Eigenvalue location in cographs, The chromatic symmetric functions of trivially perfect graphs and cographs, Oriented coloring on recursively defined digraphs, Monotonicity and expansion of global secure sets, On the structure of (\(P_{5}\),\,gem)-free graphs, Linear-time modular decomposition of directed graphs, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, Systems of distant representatives, Path partition for graphs with special blocks, Limits of structures and the example of tree semi-lattices, On graphs with distance Laplacian spectral radius of multiplicity \(n-3\), The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations, On characterizations for subclasses of directed co-graphs, Contraction and deletion blockers for perfect graphs and \(H\)-free graphs, Parameterized algorithms for conflict-free colorings of graphs, Minimal obstructions to \(( \infty , k )\)-polarity in cographs, Graphs with some distance Laplacian eigenvalue of multiplicity \(n-3\), Representing graphs as the intersection of cographs and threshold graphs, Indirect identification of horizontal gene transfer, Hamiltonicity in graphs with few \(P_ 4\)'s, An optimal parallel algorithm for node ranking of cographs, Weighted connected domination and Steiner trees in distance-hereditary graphs, Twin-width and generalized coloring numbers, Exact values of defective Ramsey numbers in graph classes, Triangulating graphs with few \(P_4\)'s, Partial and perfect path covers of cographs, Achromatic number is NP-complete for cographs and interval graphs, Unavoidable doubly connected large graphs, From modular decomposition trees to rooted median graphs, Towards the reconstruction of posets, Permutations, parenthesis words, and Schröder numbers, Tree-like \(P_4\)-connected graphs, Hamiltonian powers in threshold and arborescent comparability graphs, Modular decomposition and transitive orientation, Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time., Exploring symmetries in cographs: obtaining spectra and energies, A linear time algorithm for the maximum matching problem on cographs, On cocolourings and cochromatic numbers of graphs, Generalizing cographs to 2-cographs, On \(m\)-centers in \(P_ t\)-free graphs, Conflict-free coloring: graphs of bounded clique width and intersection graphs, Vertex cover at distance on \(H\)-free graphs

Cites Work