Each 11-vertex graph without 4-cliques has a triangle-free 2-partition of vertices

Abstract

Let $G$ be a graph, $\text{cl}(G)$ denotes the clique number of the graph $G$. By $G\to (3,3)$ we denote that in any 2-partition $V_1\cup V_2$ of the set $V(G)$ of his vertices either $V_1$ or $V_2$ contains 3-clique (triangle) of the graph $G;\alpha =min|V(G)|,G\to (3,3)\text{ and cl}(G)=4,\beta =min|V(G)|,G\to (3,3)\text{ and cl}(G)=3$. In the current article, we consider graphs $G$ with the property $G\to (3,3)$. As a consequence from proven results it follows that $\alpha =8\text{ and }\beta \ge 12$.