Entropy splitting for antiblocking corners and perfect graphs
From MaRDI portal
Publication:810528
DOI10.1007/BF02122693zbMath0734.05061OpenAlexW1977529491WikidataQ100603844 ScholiaQ100603844MaRDI QIDQ810528
Imre Csiszár, László Lovász, János Körner, Gábor Simonyi, Katalin Marton
Publication date: 1990
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02122693
Coloring of graphs and hypergraphs (05C15) Graph theory (05C99) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (31)
Information theoretic parameters of noncommutative graphs and convex corners ⋮ On equistable, split, CIS, and related classes of graphs ⋮ Almost all regular graphs are normal ⋮ An ergodic theorem for constrained sequences of functions ⋮ Attempting perfect hypergraphs ⋮ Generalizing Körner's graph entropy to graphons ⋮ A history of graph entropy measures ⋮ A Sum of Squares Characterization of Perfect Graphs ⋮ Line-graphs of cubic graphs are normal ⋮ The normal graph conjecture for two classes of sparse graphs ⋮ Sorting under partial information (without the ellipsoid algorithm). ⋮ Disproving the normal graph conjecture ⋮ Structural information content of networks: graph entropy based on local vertex functionals ⋮ Symmetric graphs with respect to graph entropy ⋮ Perfect couples of graphs ⋮ An axiomatic duality framework for the theta body and related convex corners ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ Minimum entropy combinatorial optimization problems ⋮ Some bounds of weighted entropies with augmented Zagreb index edge weights ⋮ Sandwich theorems and capacity bounds for non-commutative graphs ⋮ Energy of convex sets, shortest paths, and resistance ⋮ ``Cone-free primal-dual path-following and potential-reduction polynomial time interior-point methods ⋮ Linear extensions and comparable pairs in partial orders ⋮ Poset entropy versus number of linear extensions: the width-2 case. ⋮ Constructions for normal graphs and some consequences ⋮ Unnamed Item ⋮ On the capacity of Boolean graph formulæ ⋮ Probabilistic refinement of the asymptotic spectrum of graphs ⋮ A NOVEL METHOD FOR MEASURING THE STRUCTURAL INFORMATION CONTENT OF NETWORKS ⋮ On the odd cycles of normal graphs ⋮ On Generalized Comparison-Based Sorting Problems
Cites Work
- Relaxations of vertex packing
- New bounds for perfect hashing via information theory
- On the Shannon capacity of probabilistic graphs
- On certain polytopes associated with graphs
- Fredman–Komlós bounds and information theory
- On the Shannon capacity of a graph
- Two-step encoding for finite sources
- Blocking and anti-blocking pairs of polyhedra
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Entropy splitting for antiblocking corners and perfect graphs
