Properly colored short cycles in edge-colored graphs. (February 2022)
- Record Type:
- Journal Article
- Title:
- Properly colored short cycles in edge-colored graphs. (February 2022)
- Main Title:
- Properly colored short cycles in edge-colored graphs
- Authors:
- Ding, Laihao
Hu, Jie
Wang, Guanghui
Yang, Donglei - Abstract:
- Abstract: Properly colored cycles in edge-colored graphs are closely related to directed cycles in oriented graphs. As an analogy of the well-known Caccetta–Häggkvist Conjecture, we study the existence of properly colored cycles of bounded length in an edge-colored graph. We first prove that for all integers s and t with t ≥ s ≥ 2, every edge-colored graph G with no properly colored K s, t contains a spanning subgraph H which admits an orientation D such that every directed cycle in D is a properly colored cycle in G . Using this result, we show that for r ≥ 4, if the Caccetta–Häggkvist Conjecture holds, then every edge-colored graph of order n with minimum color degree at least n / r + 2 n + 1 contains a properly colored cycle of length at most r . In addition, we also obtain an asymptotically tight total color degree condition which ensures a properly colored (or rainbow) K s, t .
- Is Part Of:
- European journal of combinatorics. Volume 100(2022)
- Journal:
- European journal of combinatorics
- Issue:
- Volume 100(2022)
- Issue Display:
- Volume 100, Issue 2022 (2022)
- Year:
- 2022
- Volume:
- 100
- Issue:
- 2022
- Issue Sort Value:
- 2022-0100-2022-0000
- Page Start:
- Page End:
- Publication Date:
- 2022-02
- Subjects:
- Combinatorial analysis -- Periodicals
Analyse combinatoire -- Périodiques
Combinatorial analysis
Periodicals
Electronic journals
511.6 - Journal URLs:
- http://www.sciencedirect.com/science/journal/01956698 ↗
http://www.elsevier.com/journals ↗
http://www.idealibrary.com ↗
http://firstsearch.oclc.org ↗
http://firstsearch.oclc.org/journal=0195-6698;screen=info;ECOIP ↗ - DOI:
- 10.1016/j.ejc.2021.103436 ↗
- Languages:
- English
- ISSNs:
- 0195-6698
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3829.728200
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 22662.xml