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

TitleEach 11-vertex graph without 4-cliques has a triangle-free 2-partition of vertices
Publication TypeJournal Article
Year of Publication1999
AuthorsNedialkov E, Nenov N
JournalAnnuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique
Volume91
IssueLivre 1 - Mathématiques et Mecanique
Pagination127-147
ISSN0205-0808
Keywordschromatic 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

AttachmentSize
PDF icon 91-127-147.pdf2.18 MB