Solutions to Edmonds' and Katona's problems on families of separating subsets

DOI10.1016/0012-365X(83)90068-7zbMath0498.05051MaRDI QIDQ1171074

Mao-cheng Cai

Publication date: 1983

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

zbMATH Keywords

chromatic numberNP-completedecomposition 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)

Related Items

How robust is the n-cube? ⋮ On separating systems of graphs

Cites Work

• On a problem of Katona on minimal separating systems
• Unnamed Item