Strict chordal and strict split digraphs

DOI10.1016/J.DAM.2016.02.009zbMATH Open1358.05125OpenAlexW2298045254WikidataQ59815572 ScholiaQ59815572MaRDI QIDQ516787FDOQ516787

César Hernández-Cruz, Pavol Hell

Publication date: 15 March 2017

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

Full work available at URL: https://doi.org/10.1016/j.dam.2016.02.009

zbMATH Keywords

recognition algorithmsplit digraphchordal digraphperfect digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Interval digraphs: An analogue of interval graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• The strong perfect graph theorem
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Recognizing Berge graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• A Characterization of Comparability Graphs and of Interval Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Partitioning chordal graphs into independent sets and cliques
• The LBFS Structure and Recognition of Interval Graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Subpath acyclic digraphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Chordal digraphs
• Toward Characterization of Perfect Elimination Digraphs
• Perfect Digraphs
• Split digraphs

Cited In (6)

• Strict chordal digraphs viewed as graphs with distinguished edges
• Unit and proper bitolerance digraphs
• Strong arc decompositions of split digraphs
• Semi-strict chordal digraphs
• Semi-strict chordality of digraphs
• Splitting digraphs

This page was built for publication: Strict chordal and strict split digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516787)