The Inducibility of Graphs on Four Vertices

DOI10.1002/jgt.21733zbMath1292.05161arXiv1109.1592OpenAlexW2591779083MaRDI QIDQ5417819

James Hirst

Publication date: 22 May 2014

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

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

zbMATH Keywords

semidefinite programmingextremal graph theorypartially labeled graphsgraph inducibility

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Semidefinite programming (90C22) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Density (toughness, etc.) (05C42)

Related Items

A bound on the inducibility of cycles ⋮ Inducibility and universality for trees ⋮ On the inducibility of oriented graphs on four vertices ⋮ Maximising the number of induced cycles in a graph ⋮ The Codegree Threshold for 3-Graphs with Independent Neighborhoods ⋮ The maximum number of induced C5's in a planar graph ⋮ On the exact maximum induced density of almost all graphs and their inducibility ⋮ Stability from graph symmetrisation arguments with applications to inducibility ⋮ Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle ⋮ Further results on the inducibility of $d$-ary trees ⋮ Inducibility in the hypercube ⋮ Strong forms of stability from flag algebra calculations ⋮ The inducibility of blow-up graphs ⋮ A note on the inducibility of 4-vertex graphs ⋮ Maximum density of vertex-induced perfect cycles and paths in the hypercube ⋮ On the inducibility of cycles ⋮ Inducibility of \(d\)-ary trees ⋮ Minimum number of edges that occur in odd cycles ⋮ The feasible region of induced graphs

Cites Work

• Unnamed Item
• The inducibility of blow-up graphs
• On the maximum number of five-cycles in a triangle-free graph
• Limits of dense graph sequences
• The maximal number of induced complete bipartite graphs
• On the number of pentagons in triangle-free graphs
• Random graphons and a weak Positivstellensatz for graphs
• On 3-Hypergraphs with Forbidden 4-Vertex Configurations
• On Sets of Acquaintances and Strangers at any Party
• Reflection positivity, rank connectivity, and homomorphism of graphs
• The inducibility of complete bipartite graphs
• Undecidability of linear inequalities in graph homomorphism densities
• Flag algebras
• Counting flags in triangle-free digraphs