Entropy splitting for antiblocking corners and perfect graphs

DOI10.1007/BF02122693MaRDI QIDQ810528zbMATH OpenOpenAlexWikidataFDO

Authors Imre Csiszár, János Körner, K. Marton, Gábor Simonyi, László Lovász

Publication date 1990

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02122693

zbMATH Keywords

antiblocking pairsentropyperfect graphsprobability distribution

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph theory (05C99)

Recommendations

• Perfect couples of graphs
• Graphs that Split Entropies
• Perfection, imperfection, and graph entropy
• Perfect graphs and graph entropy: An updated survey
• On the Shannon capacity of probabilistic graphs

Cites work

• Blocking and anti-blocking pairs of polyhedra
• Fredman–Komlós bounds and information theory
• scientific article; zbMATH DE number 4033655 (Why is no real title available?)
• scientific article; zbMATH DE number 3606484 (Why is no real title available?)
• scientific article; zbMATH DE number 3453665 (Why is no real title available?)
• scientific article; zbMATH DE number 3420800 (Why is no real title available?)
• New bounds for perfect hashing via information theory
• On certain polytopes associated with graphs
• On the Shannon capacity of a graph
• On the Shannon capacity of probabilistic graphs
• Relaxations of vertex packing
• Two-step encoding for finite sources

Cited in

(31)

• Constructions for normal graphs and some consequences
• Perfect couples of graphs
• On the odd cycles of normal graphs
• The normal graph conjecture for two classes of sparse graphs
• ``Cone-free primal-dual path-following and potential-reduction polynomial time interior-point methods
• Linear extensions and comparable pairs in partial orders
• On the capacity of Boolean graph formulæ
• Some bounds of weighted entropies with augmented Zagreb index edge weights
• Sandwich theorems and capacity bounds for non-commutative graphs
• Probabilistic refinement of the asymptotic spectrum of graphs
• Information theoretic parameters of noncommutative graphs and convex corners
• Disproving the normal graph conjecture
• Almost all regular graphs are normal
• Line-graphs of cubic graphs are normal
• On generalized comparison-based sorting problems
• On equistable, split, CIS, and related classes of graphs
• An ergodic theorem for constrained sequences of functions
• Minimum entropy combinatorial optimization problems
• A NOVEL METHOD FOR MEASURING THE STRUCTURAL INFORMATION CONTENT OF NETWORKS
• Symmetric graphs with respect to graph entropy
• scientific article; zbMATH DE number 7204408 (Why is no real title available?)
• An axiomatic duality framework for the theta body and related convex corners
• Energy of convex sets, shortest paths, and resistance
• Poset entropy versus number of linear extensions: the width-2 case.
• Attempting perfect hypergraphs
• Generalizing Körner's graph entropy to graphons
• A Sum of Squares Characterization of Perfect Graphs
• A history of graph entropy measures
• On the main distance-based entropies: the eccentricity- and Wiener-entropy
• Minimum entropy combinatorial optimization problems
• Structural information content of networks: graph entropy based on local vertex functionals

This page was built for publication: Entropy splitting for antiblocking corners and perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810528)