Color degree and alternating cycles in edge-colored graphs (Q1043956): Difference between revisions

The authors consider edge-colourings \(C: E\to\mathbb{N}\) of graphs \(G= (V,E)\), where \(\mathbb{N}\) is the set of natural numbers. The colour degree \(d^C(v)\) of a vertex \(v\) is the maximum number of edges incident with \(v\) and having distinct colours. An alternating cycle of \(G\) is a cycle in \(G\) in which any two consecutive edges have distinct colours. In the paper the existence of alternating cycles with prescribed properties is studied: If \(G\) is an edge-coloured graph with \(n\geq 3\) vertices and each vertex has colour degree \(d^C(v)> {n+1\over 3}\), then \(G\) has an alternating cycle such that every colour of \(C\) occurs at most twice. If \(G\) is an edge-coloured graph with \(n\geq 3\) vertices and each vertex has colour degree \(d^C(v)>{37n-17\over 75}\), then \(G\) contains at least one alternating triangle or one alternating quadrilateral. There is the conjecture that every edge-coloured graph with \(n\geq 3\) vertices and colour degree \(\geq{n\over 2}\) for all vertices has an alternating Hamiltonian cycle.