# Upper bound on chromatic number for some graphs

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.

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

Thanks.

• The complete graphs $K_n$ are in your class, so the bound $\Delta(G)+1$ is actually tight for your class. – Tony Huynh Mar 2 '17 at 12:35
• excuse me, I forget write an important property: This class has no perfect sub-graph except $K_3$. – C.F.G Mar 2 '17 at 12:46
• What do you mean by the condition 2? No graph in your class has no perfect subgraph different from $K_3$? It is bit strange: any graph with at most 4 vertices is perfect. – Fedor Petrov Mar 2 '17 at 13:05
• If $G$ is a graph and $G$ has 4 vertices, then $G$ is perfect. No? – Fedor Petrov Mar 2 '17 at 13:19
• I made a mistake. I used "perfect" instead of "complete". sorry. – C.F.G Mar 2 '17 at 13:23

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.

• How can we compute the constant $c(H)$? – C.F.G Mar 4 '17 at 6:00

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.

• thanks for your answer. your first statement is nice and acceptable for me but i cannot accept second paragraph. – C.F.G Mar 4 '17 at 5:57

(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.