The domatic number problem on some perfect graph families

DOI10.1016/0020-0190(94)90054-XMaRDI QIDQ1313715zbMATH OpenFDO

Authors Haim Kaplan, Ron Shamir

Publication date 19 May 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)90054-X

zbMATH Keywords

bipartite graphschordal graphsdomatic numberdomatic partitionlinear time algorithmperfect graphstotally balanced hypergraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Domatic Partition on Several Classes of Graphs
• The Domatic Number Problem in Interval Graphs
• Linear algorithm for domatic number problem on interval graphs
• A note on the complexity of the total domatic partition problem in graphs
• Finding a Domatic Partition of an Interval Graph in Time $O(n)$

Cites work

• A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
• Balanced matrices
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Dominating sets and domatic number of circular arc graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Doubly lexical ordering of dense 0--1 matrices
• Doubly Lexical Orderings of Matrices
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear algorithm for domatic number problem on interval graphs
• Some simplified NP-complete graph problems
• The edge inducibility of graphs
• Three Partition Refinement Algorithms
• Totally-Balanced and Greedy Matrices

Cited in

(14)

• On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset
• Transversal partitioning in balanced hypergraphs
• The domatic number of block-cactus graphs
• Graphs with small Italian domatic number
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Independent domatic partitioning or fall coloring of strongly chordal graphs
• On the problem of domino recognition
• Maximum Connected Domatic Partition of Directed Path Graphs with Single Junction
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Finding a Domatic Partition of an Interval Graph in Time $O(n)$
• A note on the complexity of the total domatic partition problem in graphs
• NP-completeness results for partitioning a graph into total dominating sets
• An improved exact algorithm for the domatic number problem
• Finding domatic partitions in infinite graphs

This page was built for publication: The domatic number problem on some perfect graph families

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