Title | Each 11-vertex graph without 4-cliques has a triangle-free 2-partition of vertices |
Publication Type | Journal Article |
Year of Publication | 1999 |
Authors | Nedialkov E, Nenov N |
Journal | Annuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique |
Volume | 91 |
Issue | Livre 1 - Mathématiques et Mecanique |
Pagination | 127-147 |
ISSN | 0205-0808 |
Keywords | chromatic number, triangle free partition of vertices of graph |
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$. |
1991/95 MSC | 05C55, 05C35 |
Attachment | Size |
---|---|
91-127-147.pdf | 2.18 MB |