The Domatic Number Problem in Interval Graphs

DOI10.1137/0403045MaRDI QIDQ5749323zbMATH OpenOpenAlexFDO

Authors Tung-Lin Lu, Pei-Hsin Ho, Gerard Jennhwa Chang

Publication date 1990

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/563a79a36b22a5cfa1c82daa81c5dcc473af3094

zbMATH Keywords

algorithmsdomatic numberdominating setinterval graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the domatic number of interval graphs
• Linear algorithm for domatic number problem on interval graphs
• Finding a Domatic Partition of an Interval Graph in Time $O(n)$
• Total domination in interval graphs
• The domatic number problem

Cited in

(22)

• On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset
• On the domatic number of interval graphs
• A unified approach to domination problems on interval graphs
• A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
• An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model
• Linear algorithm for domatic number problem on interval graphs
• The domatic number problem on some perfect graph families
• The domatic number problem
• Edge domatic numbers of complete \(n\)-partite graphs
• The k-neighbor, r-domination problems on interval graphs
• Weighted independent perfect domination on cocomparability graphs
• Maximum Connected Domatic Partition of Directed Path Graphs with Single Junction
• The nomatic number problem in interval graphs
• Finding a Domatic Partition of an Interval Graph in Time $O(n)$
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• The upper domatic number of a graph
• Domatically perfect graphs
• Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs
• Domatically full Cartesian product graphs
• Loose cover of graphs
• A resource assignment problem on graphs
• A tight bound on the number of mobile servers to guarantee transferability among dominating configurations

This page was built for publication: The Domatic Number Problem in Interval Graphs

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