Skip to main content
Corrected a technical term.
Source Link
Peter Heinig
  • 6.1k
  • 1
  • 27
  • 47

Apart of the specific Mycielski-like construction from the article in Dominic's answer, we may take the universal triangle free-graph, which satisfies the following conditions:

(i) $G$ has countable number of vertices;

(ii) $G$ does not contain triangles;

(iii) for any finite set $V_0$ of vertices of $G$ and any independent subset $V_1\subset V_0$ there exists a vertex $u\notin V_0$ in $G$ such that $N(u)\cap V_0=V_1$. Here $N(u)$ denotes, as usual, the set of neighbours of $u$.

It is easy to achieve this by inductive procedure, and also it is easy to check that this graph is highly transitive (any partial isomorphisms between finite subgraphs may be extended to a genuine isomorphismautomorphism of the whole $G$). Also $G$ contains all finite triangle-free graphs (the vertices of such a graph may be constructed consequentially). Thus $G$ has infinite chromatic number, since the finite triangle-free subgraphs may have arbitrarily large chromatic number.

Apart of the specific Mycielski-like construction from the article in Dominic's answer, we may take the universal triangle free-graph, which satisfies the following conditions:

(i) $G$ has countable number of vertices;

(ii) $G$ does not contain triangles;

(iii) for any finite set $V_0$ of vertices of $G$ and any independent subset $V_1\subset V_0$ there exists a vertex $u\notin V_0$ in $G$ such that $N(u)\cap V_0=V_1$. Here $N(u)$ denotes, as usual, the set of neighbours of $u$.

It is easy to achieve this by inductive procedure, and also it is easy to check that this graph is highly transitive (any partial isomorphisms between finite subgraphs may be extended to a genuine isomorphism of the whole $G$). Also $G$ contains all finite triangle-free graphs (the vertices of such a graph may be constructed consequentially). Thus $G$ has infinite chromatic number, since the finite triangle-free subgraphs may have arbitrarily large chromatic number.

Apart of the specific Mycielski-like construction from the article in Dominic's answer, we may take the universal triangle free-graph, which satisfies the following conditions:

(i) $G$ has countable number of vertices;

(ii) $G$ does not contain triangles;

(iii) for any finite set $V_0$ of vertices of $G$ and any independent subset $V_1\subset V_0$ there exists a vertex $u\notin V_0$ in $G$ such that $N(u)\cap V_0=V_1$. Here $N(u)$ denotes, as usual, the set of neighbours of $u$.

It is easy to achieve this by inductive procedure, and also it is easy to check that this graph is highly transitive (any partial isomorphisms between finite subgraphs may be extended to a genuine automorphism of the whole $G$). Also $G$ contains all finite triangle-free graphs (the vertices of such a graph may be constructed consequentially). Thus $G$ has infinite chromatic number, since the finite triangle-free subgraphs may have arbitrarily large chromatic number.

added 9 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Apart of the specific Mycielski-like construction from the article in Dominic's answer, we may take the universal triangle free-graph, which satisfies the following conditions:

(i) $G$ has countable number of vertices;

(ii) $G$ does not contain triangles;

(iii) for any finite set $V_0$ of vertices of $G$ and any independent subset $V_1\subset V_0$ there exists a vertex $u\notin V_0$ in $G$ such that $N(u)\cap V_0=V_1$. Here $N(u)$ denotes, as usual, the set of neighbours of $u$.

It is easy to achieve this by inductive procedure, and also it is easy to check that this graph is highly transitive (any partial isomorphisms between finite subgraphs may be extended to a genuine isomorphism of the whole $G$). Also $G$ contains all finite triangle-free graphs (the vertices of such a graph may be constructed consequentially). Thus $G$ has infinite chromatic number, since the finite triangle-free subgraphs may have infinitearbitrarily large chromatic number.

Apart of the specific Mycielski-like construction from the article in Dominic's answer, we may take the universal triangle free-graph, which satisfies the following conditions:

(i) $G$ has countable number of vertices;

(ii) $G$ does not contain triangles;

(iii) for any finite set $V_0$ of vertices of $G$ and any independent subset $V_1\subset V_0$ there exists a vertex $u\notin V_0$ in $G$ such that $N(u)\cap V_0=V_1$. Here $N(u)$ denotes, as usual, the set of neighbours of $u$.

It is easy to achieve this by inductive procedure, and also it is easy to check that this graph is highly transitive (any partial isomorphisms between finite subgraphs may be extended to a genuine isomorphism of the whole $G$). Also $G$ contains all finite triangle-free graphs (the vertices of such a graph may be constructed consequentially). Thus $G$ has infinite chromatic number, since the finite triangle-free subgraphs may have infinite chromatic number.

Apart of the specific Mycielski-like construction from the article in Dominic's answer, we may take the universal triangle free-graph, which satisfies the following conditions:

(i) $G$ has countable number of vertices;

(ii) $G$ does not contain triangles;

(iii) for any finite set $V_0$ of vertices of $G$ and any independent subset $V_1\subset V_0$ there exists a vertex $u\notin V_0$ in $G$ such that $N(u)\cap V_0=V_1$. Here $N(u)$ denotes, as usual, the set of neighbours of $u$.

It is easy to achieve this by inductive procedure, and also it is easy to check that this graph is highly transitive (any partial isomorphisms between finite subgraphs may be extended to a genuine isomorphism of the whole $G$). Also $G$ contains all finite triangle-free graphs (the vertices of such a graph may be constructed consequentially). Thus $G$ has infinite chromatic number, since the finite triangle-free subgraphs may have arbitrarily large chromatic number.

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Apart of the specific Mycielski-like construction from the article in Dominic's answer, we may take the universal triangle free-graph, which satisfies the following conditions:

(i) $G$ has countable number of vertices;

(ii) $G$ does not contain triangles;

(iii) for any finite set $V_0$ of vertices of $G$ and any independent subset $V_1\subset V_0$ there exists a vertex $u\notin V_0$ in $G$ such that $N(u)\cap V_0=V_1$. Here $N(u)$ denotes, as usual, the set of neighbours of $u$.

It is easy to achieve this by inductive procedure, and also it is easy to check that this graph is highly transitive (any partial isomorphisms between finite subgraphs may be extended to a genuine isomorphism of the whole $G$). Also $G$ contains all finite triangle-free graphs (the vertices of such a graph may be constructed consequentially). Thus $G$ has infinite chromatic number, since the finite triangle-free subgraphs may have infinite chromatic number.