Extremal graphs for homomorphisms

DOI10.1002/jgt.20530zbMath1231.05132OpenAlexW2004655495MaRDI QIDQ5199417

Jonathan Cutler, Andrew John Radcliffe

Publication date: 16 August 2011

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20530

zbMATH Keywords

homomorphismsextremal problemthreshold graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Extremal graphs for the Tutte polynomial ⋮ Homomorphisms into loop-threshold graphs ⋮ Dr. Charles L. Suffel: Scholar, teacher, mentor, friend ⋮ On 4-Sachs optimal graphs ⋮ Two problems on independent sets in graphs ⋮ Graph vulnerability parameters, compression, and threshold graphs ⋮ Graph vulnerability parameters, compression, and quasi-threshold graphs ⋮ Sidorenko's conjecture, colorings and independent sets ⋮ Enumerating threshold graphs and some related graph classes ⋮ Graphs with the fewest matchings ⋮ Maximizing H‐Colorings of a Regular Graph ⋮ Extremal Graphs for Homomorphisms II ⋮ Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree ⋮ Colored graph homomorphisms ⋮ Homomorphisms of Trees into a Path ⋮ Extremal H‐Colorings of Graphs with Fixed Minimum Degree

Cites Work

• Unnamed Item
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Legal coloring of graphs
• Nonmonotonic behavior in hard-core and Widom-Rowlinson models
• A monotonicity result for hard-core and Widom-Rowlinson models on certain \(d\)-dimensional lattices
• Threshold graphs and related topics
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• Entropy, independent sets and antichains: A new approach to Dedekind’s problem
• Maximizing the number of q -colorings
• Reflection positivity, rank connectivity, and homomorphism of graphs
• On the greatest number of 2 and 3 colorings of a (v, e)-graph

This page was built for publication: Extremal graphs for homomorphisms