The domatic number problem on some perfect graph families

DOI10.1016/0020-0190(94)90054-XzbMath0787.68080MaRDI QIDQ1313715

Ron Shamir, Haim Kaplan

Publication date: 19 May 1994

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

zbMATH Keywords

bipartite graphsperfect graphslinear time algorithmchordal graphsdomatic numbertotally balanced hypergraphsdomatic partition

Mathematics Subject Classification ID

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

Related Items (9)

Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration ⋮ An improved exact algorithm for the domatic number problem ⋮ Transversal partitioning in balanced hypergraphs ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ Finding domatic partitions in infinite graphs ⋮ Graphs with small Italian domatic number ⋮ NP-completeness results for partitioning a graph into total dominating sets ⋮ On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset ⋮ The domatic number of block-cactus graphs

Cites Work

• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Characterizations of strongly chordal graphs
• Dominating sets and domatic number of circular arc graphs
• A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
• Some simplified NP-complete graph problems
• Linear algorithm for domatic number problem on interval graphs
• Doubly lexical ordering of dense 0--1 matrices
• Characterizations of totally balanced matrices
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• Three Partition Refinement Algorithms
• The edge inducibility of graphs
• Balanced matrices

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