Skip to main content
Source Link
Tony Huynh
  • 32.9k
  • 12
  • 121
  • 190

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.