Skip to main content
2 of 6
added 61 characters in body
C.F.G
  • 4.2k
  • 6
  • 38
  • 67

Upper bound on chromatic number for some graphs

I am beginner in graph theory and I interested in finding upper bound for chromatic number of the following class of graphs:

  1. If two vertices $a$ and $b$ are adjacent in $G$, then there exist vertex $c$ such that $abc$ is a triangle graph. In other words, there exist vertex $c$ such that $c$, $a$ and $b$ are adjacent.
  2. This class has no perfect sub-graph except $K_3$.

for example chromatic number of triangle is $\chi(G)=3$. In general, an upper bound for chromatic number of arbitrary graph $G$ is $\Delta(G)+1$; But this bound is not best for the above problem.

Is there any paper about this problem?

Thanks.

C.F.G
  • 4.2k
  • 6
  • 38
  • 67