The Bipartite Swapping Trick on Graph Homomorphisms

DOI10.1137/100800415zbMath1232.05139arXiv1104.3704OpenAlexW2106299455MaRDI QIDQ3094936

Yufei Zhao

Publication date: 27 October 2011

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

Full work available at URL: https://arxiv.org/abs/1104.3704

zbMATH Keywords

graph coloringstable set polytopeindependent setgraph homomorphism

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (13)

On replica symmetry of large deviations in random graphs ⋮ Extremal Regular Graphs: Independent Sets and Graph Homomorphisms ⋮ Sub-Fibonacci behavior in numerical semigroup enumeration ⋮ Counting numerical semigroups by Frobenius number, multiplicity, and depth ⋮ On the Widom–Rowlinson Occupancy Fraction in Regular Graphs ⋮ Maximizing the number of \(x\)-colorings of 4-chromatic graphs ⋮ The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph ⋮ Maximizing H‐Colorings of a Regular Graph ⋮ Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree ⋮ The number of independent sets in an irregular graph ⋮ A reverse Sidorenko inequality ⋮ Extremal H‐Colorings of Graphs with Fixed Minimum Degree ⋮ Counting colorings of a regular graph

This page was built for publication: The Bipartite Swapping Trick on Graph Homomorphisms