Color degree and alternating cycles in edge-colored graphs
type: Item
instance of: scholarly article
title: Color degree and alternating cycles in edge-colored graphs
zbMATH Open document ID: 1198.05070
author: Hao Li
author: Guanghui Wang
published in: Discrete Mathematics
publication date: 2009-12-10T00:00:00Z
review text: 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.
reviewed by: Ulrike Baumann
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 5644952
zbMATH Keywords: alternating cycle
zbMATH Keywords: color degree
zbMATH Keywords: Hamiltonian cycle
MaRDI profile type: Publication
full work available at URL: j.disc.2009.01.016
OpenAlex ID: W2110990225
cites work: Q3786318
cites work: Hamiltonian circuits determining the order of chromosomes
cites work: Q4836076
cites work: Alternating cycles and paths in edge-coloured multigraphs: A survey
cites work: A note on alternating cycles in edge-coloured graphs
cites work: Alternating cycles in edge-partitioned graphs
cites work: Alternating Hamiltonian cycles
cites work: Graphs with Hamiltonian cycles having adjacent lines different colours
cites work: A property of the colored complete graph
cites work: Q4358434
cites work: Long Alternating Cycles in Edge-Colored Complete Graphs
cites work: Q4192089
DOI: 10.1016/J.DISC.2009.01.016
description: scientific article; zbMATH DE number 5644952