𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Characterization of edge-colored complete graphs with properly colored Hamilton paths

✍ Scribed by Jinfeng Feng; Hans-Erik Giesen; Yubao Guo; Gregory Gutin; Tommy Jensen; Arash Rafiey

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
164 KB
Volume
53
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An edge‐colored graph H is properly colored if no two adjacent edges of H have the same color. In 1997, J. Bang‐Jensen and G. Gutin conjectured that an edge‐colored complete graph G has a properly colored Hamilton path if and only if G has a spanning subgraph consisting of a properly colored path C~0~ and a (possibly empty) collection of properly colored cycles C~1~,C~2~,…, C~d~ such that $V (C_i) \cap {V(C}_j) =\emptyset$ provided $0 \le i < j \le d$. We prove this conjecture. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 333–346, 2006

📜 SIMILAR VOLUMES

Properly colored hamilton cycles in edge
Properly colored hamilton cycles in edge-colored complete graphs
✍ N. Alon; G. Gutin 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB 👁 3 views

It is shown that, for ⑀ ) 0 and n ) n ⑀ , any complete graph K on n vertices 0 ' Ž . whose edges are colored so that no vertex is incident with more than 1 y 1r 2 y ⑀ n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and

Cycles and paths in edge-colored graphs
Cycles and paths in edge-colored graphs with given degrees
✍ A. Abouelaoualim,; K. Ch. Das; W. Fernandez de la Vega; M. Karpinski; Y. Manouss 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 203 KB 👁 1 views

## Abstract Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order __n__ on at least three colors and with minimum colored degre

Edge colorings of complete graphs withou
Edge colorings of complete graphs without tricolored triangles
✍ András Gyárfás; Gábor Simony 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 59 KB

## Abstract We show some consequences of results of Gallai concerning edge colorings of complete graphs that contain no tricolored triangles. We prove two conjectures of Bialostocki and Voxman about the existence of special monochromatic spanning trees in such colorings. We also determine the size

Designs with mutually orthogonal resolut
Designs with mutually orthogonal resolutions and decompositions of edge-colored graphs
✍ E. R. Lamken 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB

## Abstract Two resolutions __R__ and __R__^′^ of a combinatorial design are called orthogonal if |__R__~__i__~∩__R__|≤1 for all __R__~__i__~∈__R__ and __R__∈__R__^′^. A set __Q__={__R__^1^, __R__^2^, …, __R__^__d__^} of __d__ resolutions of a combinatorial design is called a set of mutually orthog

Almost regular edge colorings and regula
Almost regular edge colorings and regular decompositions of complete graphs
✍ Darryn Bryant; Barbara Maenhaut 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract For __k__ = 1 and __k__ = 2, we prove that the obvious necessary numerical conditions for packing __t__ pairwise edge‐disjoint __k__‐regular subgraphs of specified orders __m__~1~,__m__~2~,… ,__m__~t~ in the complete graph of order __n__ are also sufficient. To do so, we present an edge