Triply existentially complete triangle-free graphs

DOI10.1002/JGT.21808MaRDI QIDQ4982291zbMATH OpenOpenAlexFDO

Authors Chaim Even-Zohar, Nathan Linial

Publication date 24 March 2015

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

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

zbMATH Keywords

combinatorial problemsfinite homogeneitystable homogeneous structures

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Model theory of finite structures (03C13) Directed graphs (digraphs), tournaments (05C20) Generalized Ramsey theory (05C55)

Abstract: A triangle-free graph G is called k-existentially complete if for every induced k-vertex subgraph H of G, every extension of H to a (k+1)-vertex triangle-free graph can be realized by adding another vertex of G to H. Cherlin asked whether k-existentially complete triangle-free graphs exist for every k. Here we present known and new constructions of 3-existentially complete triangle-free graphs.

Recommendations

• On existentially complete triangle-free graphs
• Steiner triple systems and existentially closed graphs
• Triangle-free regular graphs
• Triangle-free graphs with six non-zero eigenvalues
• Forbidden triples involving the complete bipartite graph with partite sets having cardinalities two and three.

Cites work

• 2-colorings of complete graphs with a small number of monochromatic \(K_ 4\) subgraphs
• A family of countable homogeneous graphs
• A prolific construction of strongly regular graphs with the n-e. c. property
• Asymmetric graphs
• Characterization of a class of triangle-free graphs with a certain adjacency property
• Graphs which contain all small graphs
• Graphs whose every independent set has a common neighbour
• scientific article; zbMATH DE number 125198 (Why is no real title available?)
• scientific article; zbMATH DE number 2187692 (Why is no real title available?)
• On 2-e.c. graphs, tournaments, and hypergraphs
• On the construction of certain graphs
• Paley graphs satisfy all first-order adjacency axioms
• The binding number of a graph and its Anderson number
• The search for N-e.c. Graphs
• Two problems on homogeneous structures, revisited
• Über ein Extremalproblem der Graphentheorie
• Universal graphs and universal functions
• Which trees are link graphs?

Cited in

(6)

• On existentially complete triangle-free graphs
• Empty triangles in complete topological graphs
• scientific article; zbMATH DE number 1496606 (Why is no real title available?)
• Ramsey expansions of metrically homogeneous graphs
• A constructive characterization of 3-connected triangle-free graphs
• Henson graphs and Urysohn-Henson graphs as Cayley graphs

This page was built for publication: Triply existentially complete triangle-free graphs

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