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)

zbMATH Keywords

chordal graphsbipartite graphslinear time algorithmperfect graphsdomatic numbertotally balanced hypergraphsdomatic partition

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

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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 Orderings of Matrices
• Doubly lexical ordering of dense 0--1 matrices
• 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

(13)

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