The following graph property has come up naturally in some work I've been doing, and it seems like something that may have already been studied.

Namely, let $G$ be a graph with no loops or double edges, such that given any two edges $e, e'$, there exist triangles $T_1, ..., T_n$ in $G$ such that $e\in T_1, e'\in T_n$, and $T_i$ and $T_{i+1}$ have an edge in common for all $1 \leq i < n$. Does this type of graph have a name?

Equivalently, let $T(G)$ be the graph whose vertices are the edges of $G$, with an edge $e\sim e'$ iff $e$ and $e'$ are both contained in some triangle of $G$. Then $G$ is of the type above iff $T(G)$ is connected.

In particular, I am interested in research on the chromatic numbers of such graphs.

EDIT: I figured I'd expand a bit on motivation with respect to Gjergji Zaimi's answer. Namely, I'm working on machinery which is able to reduce questions about coloring a graph $G$ to questions about coloring minor subgraphs of the type I've described. The point is that these graphs are "rigid" in the sense that contracting the edges of any proper subgraph gives rise to loops or double edges. So essentially I'm after sharp results that bound from above the chromatic numbers of such graphs in terms of properties unrelated to edge contraction--in particular bounds in terms of local properties (e.g. the existence of induced subgraphs of certain types) would be ideal.


2 Answers 2


The condition where every two vertices can be connected through a sequence of triangles sharing edges is called "strongly triangulated". The graph you ask about has a strongly triangulated line graph, which is stronger than being strongly triangulated. Another weaker property I've seen is $(3,4)$-connectivity where any two edges are connected through a sequence of edges where two consecutive ones are part of a triangle or are opposite edges of a square. Also related is the notion of "weakly triangulated" which means every edge is contained in a triangle. But after all that I don't see any reason why this should have any restriction on the chromatic number, perhaps you could specify some particular result you are after?

(Added) I still don't have an answer regarding the chromatic number, but your observation about these graphs being "rigid" reminds me of Graham's notion of "irreducible" graphs in the sense of isometric embedding. Incidentally he gives your graphs as an example of irreducible graphs. (Check out his paper "Isometric Embedding of Graphs" from 1988, available on here.)

I recently found out that the relevant notion here is that of Gallai graph ant anti-Gallai graph. In the Gallai graph of $G$ the vertex set is the set of edges in $G$ and two edges are connected if they do not span a triangle. The anti-Gallai graph is the complement of the Gallai graph in the line graph of $G$ (your $T(G)$). The standard reference for these and other similar operators on graphs seems to be Prisner's "Graph Dynamics", and here are two more results from a quick search I just did, but I'm sure you can find more. It seems that the chromatic number problem for (anti)Gallai graphs remains equally hard.

  • $\begingroup$ +1: Thanks! I'll expand a bit on motivation. $\endgroup$ Feb 3, 2011 at 23:11
  • $\begingroup$ Thanks for the edit (which I just noticed)! I'd vote this up again if I could. Of course one expects this problem to be hard, since we can (for example) triangulate a planar graph to obtain a planar graph of this type... $\endgroup$ Feb 19, 2011 at 5:54

Another related notion is that of a "locally connected" graph, in which the set of neighbors of any vertex v (excluding v itself) induces a connected subgraph. A connected and locally connected graph has connected triangles in the sense you describe.

There is a known connection with graph coloring: unlike arbitrary graphs, it's easy to test whether a graph with this property (either local connectivity or the property you describe) is 3-colorable. Just 3-color one of the triangles and greedily expand the coloring to triangles that share an edge; either you color the whole graph this way or you get stuck, in which case there is no coloring.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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