Long properly coloured cycles in edge-coloured graphs

Allan Lo

doi:10.1002/jgt.22405

Long properly coloured cycles in edge-coloured graphs

Allan Lo

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

201 Downloads (Pure)

Abstract

Let be an edge‐coloured graph. The minimum colour degree of is the largest integer such that, for every vertex , there are at least distinct colours on edges incident to . We say that is properly coloured if no two adjacent edges have the same colour. In this paper, we show that, for any and large, every edge‐coloured graph with contains a properly coloured cycle of length at least .

Original language	English
Pages (from-to)	416-442
Number of pages	27
Journal	Journal of Graph Theory
Volume	90
Issue number	3
Early online date	2 Nov 2018
DOIs	https://doi.org/10.1002/jgt.22405
Publication status	Published - 1 Mar 2019

Bibliographical note

Lo A. Long properly coloured cycles in edge‐coloured graphs. J Graph Theory. 2019;90:416–442. https://doi.org/10.1002/jgt.22405

Keywords

colour degree
cycle
proper edge-colouring

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1002/jgt.22405Licence: None: All rights reserved

Lo_Long_properly_coloured_graphs_Journal_of_Graph_Theory_2018
Checked for eligibility 25/10/2018 This is the peer reviewed version of the following article: Lo A. Long properly coloured cycles in edge‐coloured graphs. J Graph Theory. 2019;90:416–442. https://doi.org/10.1002/jgt.22405 , which has been published in final form at https://doi.org/10.1002/jgt.22405. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions
Accepted author manuscript, 255 KBLicence: None: All rights reserved

https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.22405Licence: None: All rights reserved

A graph theoretical approach for combinatorial designs
Lo, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/11/16 → 31/10/18
Project: Research Councils

Cite this

@article{9cc070ab97624eb29787ad742b96a7bf,

title = "Long properly coloured cycles in edge-coloured graphs",

abstract = "Let be an edge‐coloured graph. The minimum colour degree of is the largest integer such that, for every vertex , there are at least distinct colours on edges incident to . We say that is properly coloured if no two adjacent edges have the same colour. In this paper, we show that, for any and large, every edge‐coloured graph with contains a properly coloured cycle of length at least .",

keywords = "colour degree, cycle, proper edge-colouring",

author = "Allan Lo",

note = "Lo A. Long properly coloured cycles in edge‐coloured graphs. J Graph Theory. 2019;90:416–442. https://doi.org/10.1002/jgt.22405",

year = "2019",

month = mar,

day = "1",

doi = "10.1002/jgt.22405",

language = "English",

volume = "90",

pages = "416--442",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley",

number = "3",

}

TY - JOUR

T1 - Long properly coloured cycles in edge-coloured graphs

AU - Lo, Allan

N1 - Lo A. Long properly coloured cycles in edge‐coloured graphs. J Graph Theory. 2019;90:416–442. https://doi.org/10.1002/jgt.22405

PY - 2019/3/1

Y1 - 2019/3/1

N2 - Let be an edge‐coloured graph. The minimum colour degree of is the largest integer such that, for every vertex , there are at least distinct colours on edges incident to . We say that is properly coloured if no two adjacent edges have the same colour. In this paper, we show that, for any and large, every edge‐coloured graph with contains a properly coloured cycle of length at least .

AB - Let be an edge‐coloured graph. The minimum colour degree of is the largest integer such that, for every vertex , there are at least distinct colours on edges incident to . We say that is properly coloured if no two adjacent edges have the same colour. In this paper, we show that, for any and large, every edge‐coloured graph with contains a properly coloured cycle of length at least .

KW - colour degree

KW - cycle

KW - proper edge-colouring

UR - https://arxiv.org/abs/1808.04086

U2 - 10.1002/jgt.22405

DO - 10.1002/jgt.22405

M3 - Article

SN - 0364-9024

VL - 90

SP - 416

EP - 442

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Long properly coloured cycles in edge-coloured graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Projects

A graph theoretical approach for combinatorial designs

Cite this