| Заглавие | Each 11-vertex graph without 4-cliques has a triangle-free 2-partition of vertices |
| Вид публикация | Journal Article |
| Година на публикуване | 1999 |
| Автори | Nedialkov E, Nenov N |
| Списание | Annuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique |
| Том | 91 |
| Issue | Livre 1 - Mathématiques et Mecanique |
| Pagination | 127-147 |
| ISSN | 0205-0808 |
| ключови думи | chromatic number, triangle free partition of vertices of graph |
| Резюме | 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$. |
| 1991/95 MSC | 05C55, 05C35 |
| Прикачен файл | Размер |
|---|---|
| 2.18 MB |