Premium
A Dirac Type Condition for Properly Coloured Paths and Cycles
Author(s) -
Lo Allan
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21751
Subject(s) - mathematics , combinatorics , vertex (graph theory) , path (computing) , graph , enhanced data rates for gsm evolution , type (biology) , hamiltonian path , dirac (video compression format) , computer science , physics , telecommunications , ecology , biology , programming language , nuclear physics , neutrino
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 2 d 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 .