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\).
- Complete description of forbidden subgraphs in the structural domination problem
- Dominating cliques in \(P_ 5\)-free graphs
- Chromatic-index-critical graphs of orders 11 and 12
- Dominating subgraphs in graphs with some forbidden structures
- The use of elementary substructures in combinatorics
- Maximum induced matchings in graphs
- Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs
- Colouring of (P₃ P₂)-free graphs
- Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
- Color-critical graphs with independent cutset
- Coloring of a superclass of 2K₂-free graphs
- On a problem of El-Zahar and Erdős
- Coloring tournaments with few colors: algorithms and complexity
- Edge contraction and forbidden induced subgraphs
- Some results and problems on tournament structure
- On the chromatic number of a superclass of 2 K₂-free graphs
- Characterization of graphs dominated by induced paths
- Characterization of \(P_{6}\)-free graphs
- The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
- Infinite versus finite graph domination
This page was built for publication: On the existence of two non-neighboring subgraphs in a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1078191)
