On separating systems of graphs

DOI10.1016/0012-365X(84)90146-8zbMath0498.05052MaRDI QIDQ1171075

Mao-cheng Cai

Publication date: 1984

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

chromatic numberNP-completecompletely separating systemdecomposition in separating subsets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Completely separating systems of \(k\)-sets ⋮ Separating path systems for the complete graph ⋮ Two optimal strategies for active learning of causal models from interventional data

Cites Work

• Unnamed Item
• Solutions to Edmonds' and Katona's problems on families of separating subsets
• On a problem of Katona on minimal separating systems
• Minimal completely separating systems
• On a problem concerning separating systems of a finite set

This page was built for publication: On separating systems of graphs