On the existence of two non-neighboring subgraphs in a graph

DOI10.1007/BF02579243zbMath0596.05027OpenAlexW2092318469MaRDI QIDQ1078191

Paul Erdős, Mohamed H. El-Zahar

Publication date: 1985

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579243

zbMATH Keywords

non-neighboring n-chromatic subgraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (14)

Dominating subgraphs in graphs with some forbidden structures ⋮ The use of elementary substructures in combinatorics ⋮ Maximum induced matchings in graphs ⋮ Characterization of graphs dominated by induced paths ⋮ Characterization of \(P_{6}\)-free graphs ⋮ Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs ⋮ Coloring of a superclass of \(2K_2\)-free graphs ⋮ On a problem of El-Zahar and Erdős ⋮ Colouring of \((P_3 \cup P_2)\)-free graphs ⋮ The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree ⋮ Dominating cliques in \(P_ 5\)-free graphs ⋮ Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs ⋮ Infinite versus finite graph domination ⋮ Complete description of forbidden subgraphs in the structural domination problem

Cites Work

• A bound on the chromatic number of graphs without certain induced subgraphs
• On circuits and subgraphs of chromatic graphs
• Sur le coloriage des graphs

This page was built for publication: On the existence of two non-neighboring subgraphs in a graph