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

Abstract

Let $G$ be a graph, $\textrm{cl}(G)$ denotes the clique number of the graph $G$. By $G \rightarrow (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 \rightarrow (3,3) \textrm{ and cl}(G) = 4}, \beta = min{|V(G)|, G \rightarrow (3,3) \textrm { and cl}(G) = 3}$. In the current article, we consider graphs $G$ with the property $G \rightarrow (3,3)$. As a consequence from proven results it follows that $\alpha = 8 \textrm{ and } \beta \geq 12$.