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?


  • 1
    $\begingroup$ The complete graphs $K_n$ are in your class, so the bound $\Delta(G)+1$ is actually tight for your class. $\endgroup$ – Tony Huynh Mar 2 '17 at 12:35
  • $\begingroup$ excuse me, I forget write an important property: This class has no perfect sub-graph except $K_3$. $\endgroup$ – C.F.G Mar 2 '17 at 12:46
  • $\begingroup$ 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. $\endgroup$ – Fedor Petrov Mar 2 '17 at 13:05
  • $\begingroup$ If $G$ is a graph and $G$ has 4 vertices, then $G$ is perfect. No? $\endgroup$ – Fedor Petrov Mar 2 '17 at 13:19
  • $\begingroup$ I made a mistake. I used "perfect" instead of "complete". sorry. $\endgroup$ – 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.

  • $\begingroup$ How can we compute the constant $c(H)$? $\endgroup$ – 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.

  • $\begingroup$ thanks for your answer. your first statement is nice and acceptable for me but i cannot accept second paragraph. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.