A Dirac type condition for properly coloured paths and cycles

2010/08/19 by Allan Lo, Lo, Allan
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1008.3242

includes minor revisions, accepted for publication in Jorunal of Graph Theory

openalex publication_date 2010/08/19 · arxiv created 2013/06/20 · arxiv updated 2013/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let c be an edge-colouring of a graph G such that for every vertex v there are at least d ≥ 2 different colours on edges incident to v. We prove that G contains a properly coloured path of length 2d or a properly coloured cycle of length at least d+1. Moreover, if G does not contain any properly coloured cycle, then there exists a properly coloured path of length 3 × 2^d-1-2.

Related

• An edge-coloured version of Dirac's theorem
• Properly Coloured Cycles and Paths: Results and Open Problems
• Long properly coloured cycles in edge-coloured graphs
• On Induced Colourful Paths in Triangle-free Graphs
• Proper Hamiltonian Paths in Edge-Coloured Multigraphs