# Question about triangle free graphs

• titaniumx3
In summary, for a triangle-free graph G on n vertices, the chromatic number is at most 2√n+1. This is because the graph can be colored with a maximum of 2√n+1 colors, as shown by the process of creating subgraphs and minimizing the number of colors used. Each vertex in the subgraph is assigned a different color, with the maximum degree vertex being discarded at each step. This process can be repeated until all vertices are assigned a color, and the maximum number of colors used will be 2√n+1, which is the upper bound for the chromatic number of G.
titaniumx3

## Homework Statement

Prove that every triangle-free graph G on n vertices has chromatic number at most $$2\sqrt{n}+1$$.

## Homework Equations

The chromatic number of a graph G is the smallest number of colors needed to color the vertices of a graph so that no two adjacent vertices share the same color.

Trinagle-free graph means that there are no loops of length 3 contained in the graph.

## The Attempt at a Solution

For a triangle free graph G on n vertices, we know that for a vertex x_1, the neighbourhood of x_1 forms an independent set (i.e. there are no edges between any two vertices); otherwise their would be triangles.

Therefore, all vertices of the neighbourhood N(x_1) can be coloured with a single colour, say "1".

Now suppose we take the subgraph H where H = G - N(x_1) and take another vertex x_2 in H, then the neighbourhood of x_2 in H is also an independent set, hence it can be coloured with a single colour, say "2". Note that the colour may not necessarily be "1" since there may be edges between the neighbourhoods of x_1 and x_2.

If we repeat this process and define a new subgraph as before, then we can define another neighbour hood of a particular vertex and colour it with "3" and so on. Now, we can minimise the number of colours used in this process by letting the vertices x_1, x_2, x_3, ... , x_r (for some r) be the the vertex of maximum degree at each step. Hence at each step, in creating each subgraph we will discard a number of vertices amounting to the maximum degree of the the preceeding graph.

My problem now is that I can't figure out how many steps we can take and express it in terms of n.

Last edited:
Anyone? :)

## What is a triangle free graph?

A triangle free graph is a type of graph where there are no cycles of length three, meaning that there are no three vertices that are all connected to each other.

## What are some real-life applications of triangle free graphs?

Triangle free graphs can be used in social network analysis, where the absence of triangles can represent a lack of connections between individuals. They can also be used in scheduling and timetabling problems, as well as in the design of communication networks.

## How is a triangle free graph different from a complete graph?

A complete graph is a type of graph where every vertex is connected to every other vertex. In contrast, a triangle free graph does not have any three vertices that are all connected to each other. This means that a complete graph must have at least one triangle, while a triangle free graph cannot have any triangles.

## Can a triangle free graph have any cycles?

Yes, a triangle free graph can have cycles of length greater than three. However, it cannot have any cycles of length three, as that would violate the definition of a triangle free graph.

## How can I determine if a graph is triangle free?

One way to determine if a graph is triangle free is to check for the presence of any cycles of length three. If there are no such cycles, then the graph is triangle free. Another approach is to use mathematical theorems and properties of triangle free graphs to prove that a graph is triangle free.

• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
2K
• Calculus and Beyond Homework Help
Replies
3
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• General Math
Replies
21
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
4K
• Calculus and Beyond Homework Help
Replies
5
Views
3K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K