Upper bound on chromatic number for some graphs

Question

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.

Answer 1

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.

Answer 2

No, not every graph in your class is planar. Let $G$ be the graph obtained from $K_{3,3}$ by adding a new vertex that is adjacent to all vertices of $K_{3,3}$. Since, $K_{3,3}$ is triangle free, $G$ does not contain $K_4$. Moreover, it is clear that every edge of $G$ is contained in a triangle.

Your class of graphs does not have bounded chromatic number either. For example, the Mycielski Graphs are a sequence of triangle-free graphs that have arbitrarily large chromatic number. By adding an apex vertex to the Mycielski Graphs (or performing Pat Devlin's construction) you get a sequence of graphs that have unbounded chromatic number and satisfy your conditions.

Answer 3

(First, welcome to graph theory)

No, there's likely not much you can say by adding your restriction (that every edge is on a triangle).

Consider for example the following construction.

Let $G$ be any graph whatsoever (and make $G$ something ugly where you feel like you have no control over the chromatic number).

Then for each edge, create a new vertex and attach it to both ends of that edge (thereby putting every edge on a triangle).

This doesn't change the chromatic number [provided $G$ wasn't bipartite] or the clique number [provided $G$ had triangles], and it changes the max degree by doubling it. So anything you had controlling the chromatic number shouldn't involve parameters unaffected by this operation.