2
$\begingroup$

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.

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

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ How can we compute the constant $c(H)$? $\endgroup$ Commented Mar 4, 2017 at 6:00
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks for your answer. your first statement is nice and acceptable for me but i cannot accept second paragraph. $\endgroup$ Commented Mar 4, 2017 at 5:57
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.