Compatible Hamilton cycles in Dirac graphs (Q681601): Difference between revisions

The famous theorem of Dirac states that graphs on \(n\) vertices with minimum degree \(\delta \geq \frac{n}{2}\) (\(=\) Dirac graphs) are Hamiltonian. In this paper, a much stronger result showing that Dirac's graphs are robust against forbidden pairs of edges is presented: Let for each vertex \(v\) of a graph \(G\) a system of forbidden pairs of edges incident to \(v\) be given. Then there exists an absolute constant \(c\) such that each Dirac graph \(G\) contains a Hamiltonian cycle avoiding all forbidden pairs of edges, assuming that each edge occurs in at most \(cn\) forbidden pairs.