Perfect graphs and graph entropy: An updated survey
This survey paper is an updated version of an earlier paper [\textit{G. Simonyi}, Graph entropy: A survey. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 20, 399-441 (1995; Zbl 0828.05001)] by the same author. In the paper, three equivalent definitions are given for the notion of graph entropy, a real valued function on finite graphs with a probability measure on its vertex set. A connection to information theory and to the theory of perfect graphs is explained. It is indicated how graph entropy can be used in the problem of sorting. The notion of graph entropy can be generalized to hypergraphs. This generalized notion is applied to the job scheduling problem. It is pointed out that the Shannon capacity and its generalization, the Sperner capacity also have close connection to graph entropy.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].
- Constructions for normal graphs and some consequences
- Minimum entropy coloring
- Perfect couples of graphs
- Reconstructing unrooted phylogenetic trees from symbolic ternary metrics
- The normal graph conjecture for two classes of sparse graphs
- Linear extensions and comparable pairs in partial orders
- Probabilistic refinement of the asymptotic spectrum of graphs
- Information theoretic parameters of noncommutative graphs and convex corners
- Computational analysis of topological index-based entropies of carbon nanotube \(Y\)-junctions
- Disproving the normal graph conjecture
- Three-way symbolic tree-maps and ultrametrics
- Extremality of graph entropy based on degrees of uniform hypergraphs with few edges
- Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth
- Line-graphs of cubic graphs are normal
- Perfection, imperfection, and graph entropy
- Rainbow saturation and graph capacities
- Randomly colouring graphs (a combinatorial view)
- scientific article; zbMATH DE number 780788 (Why is no real title available?)
- 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
- Cross‐intersecting couples of graphs
- Communication Lower Bounds Via the Chromatic Number
- Graph pairs and their entropies: Modularity problems
- Generalizing Körner's graph entropy to graphons
- A history of graph entropy measures
- Entropy splitting for antiblocking corners and perfect graphs
- Entropy of symmetric graphs
- Structural information content of networks: graph entropy based on local vertex functionals
This page was built for publication: Perfect graphs and graph entropy: An updated survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2758342)
