On the existence of two non-neighboring subgraphs in a graph
type: Item
instance of: scholarly article
title: On the existence of two non-neighboring subgraphs in a graph
zbMATH Open document ID: 0596.05027
DOI: 10.1007/BF02579243
author: Mohamed H. El-Zahar
author: P. Erdős
published in: Combinatorica
publication date: 1985-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3959456
zbMATH Keywords: non-neighboring n-chromatic subgraphs
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
cites work: Sur le coloriage des graphs
cites work: A bound on the chromatic number of graphs without certain induced subgraphs
cites work: On circuits and subgraphs of chromatic graphs
full work available at URL: https://doi.org/10.1007/bf02579243
OpenAlex ID: W2092318469
description: scientific article; zbMATH DE number 3959456