Complement reducible graphs

No abstract is available for this paper.

• Publication year

  1981

• Venue

  Discrete Applied Mathematics

• Publication date

  1981-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0166-218X(81)90013-5
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Isomorphism Testing in Hookup Classes

  1982cited by this paper
• A class of threshold and domishold graphs: equistable and equidominating graphs

  1980cited by this paper
• Algorithmic graph theory and perfect graphs

  1980cited by this paper
• The recognition of Series Parallel digraphs

  1979cited by this paper
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism

  1979cited by this paper
• Graph Theory with Applications

  1978cited by this paper
• On a class of posets and the corresponding comparability graphs

  1978cited by this paper
• Graph isomorphism and self-complementary graphs

  1978cited by this paper
• A note on a paper by D. Seinsche

  1976cited by this paper
• On a property of the class of n-colorable graphs

  1974cited by this paper
• Linear time algorithm for isomorphism of planar graphs (Preliminary Report)

  1974cited by this paper
• Isomorphism of Planar Graphs

  1972cited by this paper
• On cliques in graphs

  1965cited by this paper
• A note on “The comparability graph of a tree”

  1965cited by this paper
• A Characterization of Comparability Graphs and of Interval Graphs

  1964cited by this paper
• The comparability graph of a tree

  1962cited by this paper
• Introduction to Combinatorial Analysis

  1958cited by this paper

• Characterization of double-arborescences and their minimum length word-representants

  2026cites this paper
• Minimal toughness in subclasses of weakly chordal graphs

  2026cites this paper
• Factorization algebras in quite a lot of generality

  2026cites this paper
• Poisson-Dirichlet graphons and permutons

  2026cites this paper
• On the minimum number of eigenvalues of matrices associated with cographs

  2026cites this paper
• Graph classes with few P 4 's: Universality and Brownian graphon limits

  2026cites this paper
• Weighted efficient domination for P8-free bipartite graphs in polynomial time

  2026cites this paper
• Totally $\Delta$-Modular Tree Decompositions of Graphic Matrices for Integer Programming

  2026influential citation
• Weisfeiler-Leman on graphs of small twin-width

  2026cites this paper
• Bipartite Tur\'an problem on cographs

  2026cites this paper
• Kalai's flag conjecture for locally anti-blocking polytopes

  2025cites this paper
• Distance Laplacian spectra of graphs: A survey

  2025cites this paper
• The structure of $\Delta(1, 2, 2)$-free tournaments

  2025cites this paper
• Characterizing and computing in linear time mutual-visibility parameters in distance-hereditary graphs

  2025cites this paper
• Formulas as Processes, Deadlock-Freedom as Choreographies (Extended Version)

  2025cites this paper
• Edge-apexing in hereditary classes of graphs

  2025cites this paper
• Mader's Conjecture and Its Variants for Cographs

  2025cites this paper
• Dichotomy results for classes of countable graphs

  2025influential citation
• Bridging Treewidth and Clique-Width via Cograph-Modular-Treewidth

  2025influential citation
• Orthology and near-cographs in the context of phylogenetic networks

  2025influential citation
• Coloring Reconfiguration Under Color Swapping

  2025cites this paper
• Maya-Tupi graphs: a generalization of split graphs

  2025cites this paper
• Reconfiguring Multiple Connected Components with Size Multiset Constraints

  2025cites this paper
• Forbidden Induced Subgraph Characterization of Word-Representable Split Graphs

  2025cites this paper
• Algorithmic Aspects of Domination in Graphs

  2025cites this paper
• A combinatorial characterization of Kim's lemma for pairs of bi-invariant types

  2025cites this paper
• Spectral properties of C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {C}$$\end{document}-graphs

  2025cites this paper
• Forbidden Induced Subgraph Characterization of Word-Representable Co-bipartite Graphs

  2025cites this paper
• Enhanced power graphs of finite groups with cograph structure

  2025influential citation
• Well-hued graphs with first difference two

  2025influential citation
• On Graph Burning and Edge Burning

  2025cites this paper
• A note on the multicolour version of the Erdős-Hajnal conjecture

  2025cites this paper
• Mutual-visibility problems on graphs of diameter two

  2024cites this paper
• Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star

  2024cites this paper
• Total-rainbow connection and forbidden subgraphs

  2024cites this paper
• Almost controllable graphs and beyond

  2024cites this paper
• Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs

  2024cites this paper
• Characterizations of Italian graphs and Sicilian graphs

  2024cites this paper
• Network Representation and Modular Decomposition of Combinatorial Structures: A Galled-Tree Perspective

  2024cites this paper
• Covering and Partitioning of Split, Chain and Cographs with Isometric Paths

  2024cites this paper
• Getting linear time in graphs of bounded neighborhood diversity

  2024cites this paper
• Forbidden subgraphs on conjugacy class graphs of groups

  2024cites this paper
• Distributed Complexity of Pk-freeness: Decision and Certification

  2024cites this paper
• Partial Fitch Graphs: Characterization, Satisfiability and Complexity∗

  2024cites this paper
• Conformality of minimal transversals of maximal cliques

  2024cites this paper
• A closer look at Hamiltonicity and domination through the lens of diameter and convexity

  2024cites this paper
• Edge-apexing in hereditary classes of graphs

  2024cites this paper
• The equational theory of the Weihrauch lattice with multiplication

  2024cites this paper
• Leanness Computation: Small Values and Special Graph Classes

  2024cites this paper
• Characterization of quasi-threshold graphs with two main Q-eigenvalues

  2024cites this paper
• Fitch Graph Completion

  2023cites this paper
• Graphical Proof Theory I: Sequent Systems on Undirected Graphs

  2023cites this paper
• Computing pivot-minors

  2023cites this paper
• Stability, Vertex Stability, and Unfrozenness for Special Graph Classes

  2023influential citation
• Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and Packing Problems

  2023cites this paper
• A Game Theoretic Approach for a Minimal Secure Dominating Set

  2023cites this paper
• A SYSTEM OF INTERACTION AND STRUCTURE III: THE COMPLEXITY OF SYSTEM BV AND POMSET LOGIC

  2023cites this paper
• A note on multicolour Erd\H{o}s-Hajnal conjecture

  2023cites this paper
• Apex Graphs and Cographs

  2023influential citation
• The Upper Clique Transversal Problem

  2023cites this paper
• A SYSTEM OF INTERACTION AND STRUCTURE III: THE COMPLEXITY OF SYSTEM BV AND POMSET LOGIC

  2023cites this paper
• Recognition of chordal graphs and cographs which are Cover-Incomparability graphs

  2023cites this paper
• Induced Paths in Strongly Regular Graphs

  2023influential citation
• Laplacian spectra of cographs: A twin reduction perspective

  2023cites this paper
• Kalai's $3^{d}$ conjecture for unconditional and locally anti-blocking polytopes

  2023cites this paper
• Induced subgraph density. II. Sparse and dense sets in cographs

  2023influential citation
• More on discrete convexity

  2023cites this paper
• A linear algorithm for obtaining the Laplacian eigenvalues of a cograph

  2023cites this paper
• Solving NP-hard problems on GaTEx graphs: Linear-time algorithms for perfect orderings, cliques, colorings, and independent sets

  2023cites this paper
• Computing Optimal Leaf Roots of Chordal Cographs in Linear Time

  2023cites this paper
• Laplacian eigenvalues and eigenspaces of cographs generated by finite sequence

  2023cites this paper
• Robertson’s conjecture and universal finite generation in the homology of graph braid groups

  2023cites this paper
• New Results on Complementarity Spectra of Connected Graphs

  2023cites this paper
• Thinness and its variations on some graph families and coloring graphs of bounded thinness

  2023cites this paper
• On the computational difficulty of the terminal connection problem

  2023cites this paper
• Trivial coloring of Cartesian product of graphs

  2023cites this paper
• Adding a Tail in Classes of Perfect Graphs

  2023cites this paper
• Graph classes with few $P_4$'s: Universality and Brownian graphon limits

  2023cites this paper
• On a generalization of median graphs: k-median graphs

  2023cites this paper
• Exploring symmetries in cographs: Obtaining spectra and energies

  2023cites this paper
• On two variants of split graphs: 2-unipolar graph and k-probe-split graph

  2023cites this paper
• The Theory of Gene Family Histories

  2023cites this paper
• The Smallest Classes of Binary and Ternary Matroids Closed under Direct Sums and Complements

  2022cites this paper
• Towards a polynomial form of R¨odl’s theorem

  2022cites this paper
• Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs

  2022cites this paper
• A System of Interaction and Structure III: The Complexity of BV and Pomset Logic

  2022cites this paper
• Recognizing which Cographs are Set Graphs

  2022influential citation
• The zero forcing number of the complement of a graph

  2022cites this paper
• 2-polarity and Algorithmic Aspects of Polarity Variants on Cograph Superclasses

  2022cites this paper
• Minimal Obstructions for Polarity, Monopolarity, Unipolarity and (s, 1)-Polarity in Generalizations of Cographs

  2022influential citation
• Classification of non-solvable groups whose power graph is a cograph

  2022cites this paper
• Relationships between algebraic connectivity and vertex connectivity

  2022cites this paper
• Transducing paths in graph classes with unbounded shrubdepth

  2022cites this paper
• On the rank of the distance matrix of graphs

  2022cites this paper
• Efficient computation of oriented vertex and arc colorings of special digraphs

  2022cites this paper
• A polynomial time algorithm for geodetic hull number for complementary prisms

  2022cites this paper
• Cutting a tree with subgraph complementation is hard, except for some small trees

  2022cites this paper
• Perfect Matching Cuts Partitioning a Graph into Complementary Subgraphs

  2022cites this paper
• Graphs of bounded twin-width are quasi-polynomially χ-bounded

  2022cites this paper
• Cographs and 1-Sums

  2022influential citation