[Math] Upper bound on chromatic number for some graphs

graph theorygraph-colorings

I am a beginner in graph theory and I am interested in finding an upper bound for the 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. Every graph in this class has no complete sub-graph except $K_3$.

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

Is there any paper about this problem?

Update: Is this class of graphs planar? If not, under what additional conditions is this class of graphs planar?

Thanks.

Best Answer

For any $H$ (in particular for $K_4$) there exist a constant $c(H)$ such that the chromatic number of any $H$-free graph $G$ does not exceed $c(H)\frac{d\log\log d}{\log d}$, $d=\Delta(G)$ (provided that $d>0$). It is (conjecture 3.1.) conjectured (or already proved? oir disproved? I do not know) that double logarithm may be removed. This is proved for $H=K_3$ by Johansson. The proof is quite difficult.

Related Question