The Line Graph of the Universal Homogeneous Triangle-free Graph

2016/04/05 by Andres Aranda, Aranda, Andres
Mathematics · #F.4.1 #FOS: Mathematics #G.2.1 #Logic (math.LO) #math.LO

paper · pdf · doi:10.48550/arxiv.1604.01374

The main theorem is false

arxiv created 2021/08/26 · arxiv updated 2021/08/27

Abstract

We present some results on the structure of line graphs of triangle-free graphs and a homogenization of the line graph of the universal homogeneous triangle-free graph in a finite relational language with arity 4. This result is relevant to the study of the relational complexity of structures defined by forbidden embeddings.

Related

• The Ramsey theory of the universal homogeneous triangle-free graph Part II: Exact big Ramsey degrees
• Homomorphism-homogeneous L-colored graphs
• On the hardness of recognizing triangular line graphs
• Line graphs of Multi-Graphs and the forbidden graph E₆
• Distinguishing Number of Countable Homogeneous Relational Structures