Abstract
Does there exist a functionf(r, n) such that each graphG with Z (G)≧f(r, n) contains either a complete subgraph of orderr or else two non-neighboringn-chromatic subgraphs? It is known thatf(r, 2) exists and we establish the existence off(r, 3). We also give some interesting results about graphs which do not contain two independent edges.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Mycielski, Sur le coloriage des graphes,Colloq. Math.3 (1955), 161–162.
S. Wagon, A bound on the chromatic number of graphs without certain induced subgraphs,J. Combinatorial Theory Ser. B29 (1980), 345–346.
P. Erdős, On circuits and subgraphs of chromatic graphs,Mathematika9 (1962), 170–175.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
El-Zahar, M., Erdős, P. On the existence of two non-neighboring subgraphs in a graph. Combinatorica 5, 295–300 (1985). https://doi.org/10.1007/BF02579243
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02579243