Graph pairs and their entropies: Modularity problems

DOI10.1007/S004930070022MaRDI QIDQ5928569zbMATH OpenOpenAlexFDO

Authors János Körner, Gábor Simonyi

Publication date 1 April 2001

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

entropy of graphsfractional chromatic numberprobability distributionsubmodularity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Measures of information, entropy (94A17)

Review text

If the union of graphs \(F\), \(G\) on the same vertex set is the complete graph then for every probability distribution \(P\), the inequality \(H(F\cup G,P)+H(F\cap G,P)\leq H(F,P)+H(G,P)\) holds if and only if there is no 3-vertex set containing one edge of each of \(F-G\), \(G-F\), and \(F\cap G\), where \(H(G,P)\) is the graph entropy. \(F\) and \(G\) form a supermodular pair if and only if on no subset of the vertex set are \(F\), \(G\) edge-disjoint and imperfect. For this two proofs are given, one based on the description of the graph entropy in terms of the fractional chromatic number.

Recommendations

• Perfect couples of graphs
• Graphs that Split Entropies
• Symmetric graphs with respect to graph entropy
• Entropy of symmetric graphs
• Perfect graphs and graph entropy: An updated survey

Cited in

(21)

• Gallai-Ramsey numbers of C₇ with multiple colors
• Extremal problems and results related to Gallai-colorings
• Gallai and \(\ell \)-uniform Ramsey numbers of complete bipartite graphs
• Gallai-Ramsey number of even cycles with chords
• Gallai-Ramsey number of odd cycles with chords
• Information theoretic parameters of noncommutative graphs and convex corners
• The Erdős-Hajnal conjecture for rainbow triangles
• A note on Gallai-Ramsey number of even wheels
• Counting Gallai 3-colorings of complete graphs
• Disconnected colors in generalized Gallai-colorings
• Ramsey-type results for Gallai colorings
• Edge colorings of complete graphs without tricolored triangles
• Gallai colorings and domination in multipartite digraphs
• Gallai-Ramsey numbers of \(C_{10}\) and \(C_{12}\)
• The Typical Structure of Gallai Colorings and Their Extremal Graphs
• A conjecture on Gallai-Ramsey numbers of even cycles and paths
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• Gallai-Ramsey numbers for three graphs on at most five vertices
• The number of Gallai k-colorings of complete graphs
• Gallai colorings of non-complete graphs
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

This page was built for publication: Graph pairs and their entropies: Modularity problems

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