On the existence of two non-neighboring subgraphs in a graph
There is raised the following question: Is there a minimal integer \(f(r,n)\) such that each graph \(G\) with \(\chi(G)\geq f(r,n)\) and which does not contain a complete subgraph of order \(r\) must contain two non-neighboring \(n\)-chromatic subgraphs? It is known that \(f(r,2)\) exists. There is shown that for a fixed \(n\), an upper bound for \(f(r,n)\), \(r>n\) is given in terms of \(f(r,n)\), \(r\leq n\). From \(f(3,3)\leq 8\) is deduced an upper bound for \(f(r,3)\) and proved that a vertex critical 4-chromatic graph which does not contain two independent edges has order \(\leq 13\).
scientific article; zbMATH DE number 3959456