Paths and cycles in colored graphs

Xueliang Li; Shenggui Zhang; Hajo Broersma

doi:10.1016/S1571-0653(05)80098-8

Paths and cycles in colored graphs

Xueliang Li, Shenggui Zhang, Hajo Broersma

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

4 Citations (Scopus)

41 Downloads (Pure)

Abstract

Let G be an (edge-)colored graph. A path (cycle) is called monochromatic if all the edges of it have the same color, and is called heterochromatic if all the edges of it have different colors. In this note, some sufficient conditions for the existence of monochromatic and heterochromatic paths and cycles are obtained. We also propose a conjecture on the existence of paths and cycles with many colors.

Original language	English
Title of host publication	1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization
Subtitle of host publication	31 December 200105-31 December 200107 • Cologne, Germany
Editors	Johann Hurink, Stefan Pickl, Hajo Broersma, Ulrich Faigle
Publisher	Elsevier
Pages	128-132
DOIs	https://doi.org/10.1016/S1571-0653(05)80098-8
Publication status	Published - 2001
Event	1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001 - University of Cologne, Cologne, Germany Duration: 6 Jun 2001 → 8 Jun 2001 Conference number: 1

Publication series

Name	Electronic Notes in Discrete Mathematics
Publisher	Elsevier
Volume	8
ISSN (Print)	1571-0653

Workshop

Workshop	1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001
Abbreviated title	CTW
Country/Territory	Germany
City	Cologne
Period	6/06/01 → 8/06/01

Keywords

Monochromatic (heterochromatic) path (cycle)
(Edge-)colored graph

Access to Document

10.1016/S1571-0653(05)80098-8

Cite this

Li, X., Zhang, S., & Broersma, H. (2001). Paths and cycles in colored graphs. In J. Hurink, S. Pickl, H. Broersma, & U. Faigle (Eds.), 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization: 31 December 200105-31 December 200107 • Cologne, Germany (pp. 128-132). (Electronic Notes in Discrete Mathematics; Vol. 8). Elsevier. https://doi.org/10.1016/S1571-0653(05)80098-8

@inbook{4af13f281950460387f6320de833ff7d,

title = "Paths and cycles in colored graphs",

abstract = "Let G be an (edge-)colored graph. A path (cycle) is called monochromatic if all the edges of it have the same color, and is called heterochromatic if all the edges of it have different colors. In this note, some sufficient conditions for the existence of monochromatic and heterochromatic paths and cycles are obtained. We also propose a conjecture on the existence of paths and cycles with many colors.",

keywords = "Monochromatic (heterochromatic) path (cycle), (Edge-)colored graph",

author = "Xueliang Li and Shenggui Zhang and Hajo Broersma",

year = "2001",

doi = "10.1016/S1571-0653(05)80098-8",

language = "English",

series = "Electronic Notes in Discrete Mathematics",

publisher = "Elsevier",

pages = "128--132",

editor = "Johann Hurink and Stefan Pickl and Hajo Broersma and Ulrich Faigle",

booktitle = "1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization",

note = "1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001, CTW ; Conference date: 06-06-2001 Through 08-06-2001",

}

Li, X, Zhang, S & Broersma, H 2001, Paths and cycles in colored graphs. in J Hurink, S Pickl, H Broersma & U Faigle (eds), 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization: 31 December 200105-31 December 200107 • Cologne, Germany. Electronic Notes in Discrete Mathematics, vol. 8, Elsevier, pp. 128-132, 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001, Cologne, Germany, 6/06/01. https://doi.org/10.1016/S1571-0653(05)80098-8

Paths and cycles in colored graphs. / Li, Xueliang; Zhang, Shenggui; Broersma, Hajo.
1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization: 31 December 200105-31 December 200107 • Cologne, Germany. ed. / Johann Hurink; Stefan Pickl; Hajo Broersma; Ulrich Faigle. Elsevier, 2001. p. 128-132 (Electronic Notes in Discrete Mathematics; Vol. 8).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

TY - CHAP

T1 - Paths and cycles in colored graphs

AU - Li, Xueliang

AU - Zhang, Shenggui

AU - Broersma, Hajo

N1 - Conference code: 1

PY - 2001

Y1 - 2001

N2 - Let G be an (edge-)colored graph. A path (cycle) is called monochromatic if all the edges of it have the same color, and is called heterochromatic if all the edges of it have different colors. In this note, some sufficient conditions for the existence of monochromatic and heterochromatic paths and cycles are obtained. We also propose a conjecture on the existence of paths and cycles with many colors.

AB - Let G be an (edge-)colored graph. A path (cycle) is called monochromatic if all the edges of it have the same color, and is called heterochromatic if all the edges of it have different colors. In this note, some sufficient conditions for the existence of monochromatic and heterochromatic paths and cycles are obtained. We also propose a conjecture on the existence of paths and cycles with many colors.

KW - Monochromatic (heterochromatic) path (cycle)

KW - (Edge-)colored graph

U2 - 10.1016/S1571-0653(05)80098-8

DO - 10.1016/S1571-0653(05)80098-8

M3 - Chapter

T3 - Electronic Notes in Discrete Mathematics

SP - 128

EP - 132

BT - 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization

A2 - Hurink, Johann

A2 - Pickl, Stefan

A2 - Broersma, Hajo

A2 - Faigle, Ulrich

PB - Elsevier

T2 - 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001

Y2 - 6 June 2001 through 8 June 2001

ER -

Paths and cycles in colored graphs

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this