Classes of intersection digraphs with good algorithmic properties

DOI10.1002/jgt.23065arXiv2105.01413MaRDI QIDQ6201028

O-joung Kwon, Lars Jaffke, Jan Arne Telle

Publication date: 25 March 2024

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.01413

zbMATH Keywords

directed dominationreflexive digraphsintersection digraphs\(H\)-digraphsdirected \(H\)-homomorphism

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Homomorphisms and colourings of oriented graphs: an updated survey
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Efficient total domination in digraphs
• A new generalization of kernels in digraphs
• Solving problems on generalized convex graphs via mim-width
• Connection digraphs and second-order line digraphs
• Graph minors. X: Obstructions to tree-decomposition
• Precoloring extension. I: Interval graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Algorithms for interval catch digraphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Efficient domination of the orientations of a graph
• A width parameter useful for chordal and co-comparability graphs
• Out-degree reducing partitions of digraphs
• Degree constrained 2-partitions of semicomplete digraphs
• Directed tree-width
• On the tractability of optimization problems on \(H\)-graphs
• Linear MIM-width of trees
• On the \(k\)-domination number of digraphs
• Mim-width. III. Graph powers and generalized distance domination problems
• The rank-width of edge-coloured graphs
• Lower bounds on the mim-width of some graph classes
• Maximum \(k\)-regular induced subgraphs
• Rank-width and vertex-minors
• Finding good 2-partitions of digraphs. II. Enumerable properties
• The Directed Grid Theorem
• Interval digraphs: An analogue of interval graphs
• Circular‐arc digraphs: A characterization
• Graph Classes: A Survey
• The chromatic number of oriented graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Classes of Directed Graphs
• Independent domination in directed graphs
• Out‐colourings of digraphs
• Bipartite spanning sub(di)graphs induced by 2‐partitions
• Rank‐width is less than or equal to branch‐width
• Dominating Set and Converse Dominating Set of a Directed Graph
• On the kernel and related problems in interval digraphs

This page was built for publication: Classes of intersection digraphs with good algorithmic properties