Complement reducible graphs
From MaRDI portal
Publication:1153105
DOI10.1016/0166-218X(81)90013-5zbMath0463.05057DBLPjournals/dam/CorneilLB81OpenAlexW2028775537WikidataQ55951980 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
Related Items (only showing first 100 items - show all)
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A class of threshold and domishold graphs: Equistable and equidominating graphs
- A note on a paper by D. Seinsche
- On a class of posets and the corresponding comparability graphs
- A V log V algorithm for isomorphism of triconnected planar graphs
- On a property of the class of n-colorable graphs
- The Comparability Graph of a Tree
- Isomorphism Testing in Hookup Classes
- Dacey Graphs
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- A Note on "The Comparability Graph of a Tree"
- A Characterization of Comparability Graphs and of Interval Graphs
- On cliques in graphs
This page was built for publication: Complement reducible graphs
