Properly colored cycles in edge-colored 2-colored-triangle-free complete graphs

Shanshan Guo; Fei Huang; Jinjiang Yuan; C. T. Ng; T. C.E. Cheng

doi:10.1016/j.dam.2023.11.045

Properly colored cycles in edge-colored 2-colored-triangle-free complete graphs

Shanshan Guo, Fei Huang, Jinjiang Yuan, C. T. Ng, T. C.E. Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

Abstract

An edge-colored graph G^c is called properly colored if any two adjacent edges receive distinct colors. An edge-colored graph G^c is 2-colored-triangle-free if G^c contains no 2-colored-triangle, where a 2-colored-triangle is an edge-colored triangle with exactly two colors. Let d^c(v) be the number of colors on the edges incident to v in G^c and let δ^c(G^c) be the minimum d^c(v) for all v∈V(G^c). In this paper we extend the definitions of proper vertex-pancyclic and proper edge-pancyclic to proper k-path-pancyclic, defined as follows: An edge-colored graph G^c is said to be proper k-path-pancyclic if each properly colored path of length k is contained in a properly colored cycle of length l for every l with max{3,k+2}≤l≤|V(G^c)|. We prove that an edge-colored 2-colored-triangle-free complete graph G^c with δ^c(G^c)≥k+3 is either (almost) proper k-path-pancyclic or contains a large monochromatic complete subgraph.

Original language	English
Pages (from-to)	141-146
Number of pages	6
Journal	Discrete Applied Mathematics
Volume	345
DOIs	https://doi.org/10.1016/j.dam.2023.11.045
Publication status	Published - 15 Mar 2024

Keywords

2-colored-triangle
Color degree
Edge-coloring
Proper k-path-pancyclic
Properly colored cycle

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

More information

10.1016/j.dam.2023.11.045

Cite this

@article{0e1af9877e764adca3c1117ae053bcbf,

title = "Properly colored cycles in edge-colored 2-colored-triangle-free complete graphs",

abstract = "An edge-colored graph Gc is called properly colored if any two adjacent edges receive distinct colors. An edge-colored graph Gc is 2-colored-triangle-free if Gc contains no 2-colored-triangle, where a 2-colored-triangle is an edge-colored triangle with exactly two colors. Let dc(v) be the number of colors on the edges incident to v in Gc and let δc(Gc) be the minimum dc(v) for all v∈V(Gc). In this paper we extend the definitions of proper vertex-pancyclic and proper edge-pancyclic to proper k-path-pancyclic, defined as follows: An edge-colored graph Gc is said to be proper k-path-pancyclic if each properly colored path of length k is contained in a properly colored cycle of length l for every l with max{3,k+2}≤l≤|V(Gc)|. We prove that an edge-colored 2-colored-triangle-free complete graph Gc with δc(Gc)≥k+3 is either (almost) proper k-path-pancyclic or contains a large monochromatic complete subgraph.",

keywords = "2-colored-triangle, Color degree, Edge-coloring, Proper k-path-pancyclic, Properly colored cycle",

author = "Shanshan Guo and Fei Huang and Jinjiang Yuan and Ng, {C. T.} and Cheng, {T. C.E.}",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier B.V.",

year = "2024",

month = mar,

day = "15",

doi = "10.1016/j.dam.2023.11.045",

language = "English",

volume = "345",

pages = "141--146",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Properly colored cycles in edge-colored 2-colored-triangle-free complete graphs

AU - Guo, Shanshan

AU - Huang, Fei

AU - Yuan, Jinjiang

AU - Ng, C. T.

AU - Cheng, T. C.E.

PY - 2024/3/15

Y1 - 2024/3/15

N2 - An edge-colored graph Gc is called properly colored if any two adjacent edges receive distinct colors. An edge-colored graph Gc is 2-colored-triangle-free if Gc contains no 2-colored-triangle, where a 2-colored-triangle is an edge-colored triangle with exactly two colors. Let dc(v) be the number of colors on the edges incident to v in Gc and let δc(Gc) be the minimum dc(v) for all v∈V(Gc). In this paper we extend the definitions of proper vertex-pancyclic and proper edge-pancyclic to proper k-path-pancyclic, defined as follows: An edge-colored graph Gc is said to be proper k-path-pancyclic if each properly colored path of length k is contained in a properly colored cycle of length l for every l with max{3,k+2}≤l≤|V(Gc)|. We prove that an edge-colored 2-colored-triangle-free complete graph Gc with δc(Gc)≥k+3 is either (almost) proper k-path-pancyclic or contains a large monochromatic complete subgraph.

AB - An edge-colored graph Gc is called properly colored if any two adjacent edges receive distinct colors. An edge-colored graph Gc is 2-colored-triangle-free if Gc contains no 2-colored-triangle, where a 2-colored-triangle is an edge-colored triangle with exactly two colors. Let dc(v) be the number of colors on the edges incident to v in Gc and let δc(Gc) be the minimum dc(v) for all v∈V(Gc). In this paper we extend the definitions of proper vertex-pancyclic and proper edge-pancyclic to proper k-path-pancyclic, defined as follows: An edge-colored graph Gc is said to be proper k-path-pancyclic if each properly colored path of length k is contained in a properly colored cycle of length l for every l with max{3,k+2}≤l≤|V(Gc)|. We prove that an edge-colored 2-colored-triangle-free complete graph Gc with δc(Gc)≥k+3 is either (almost) proper k-path-pancyclic or contains a large monochromatic complete subgraph.

KW - 2-colored-triangle

KW - Color degree

KW - Edge-coloring

KW - Proper k-path-pancyclic

KW - Properly colored cycle

UR - http://www.scopus.com/inward/record.url?scp=85178995320&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2023.11.045

DO - 10.1016/j.dam.2023.11.045

M3 - Journal article

AN - SCOPUS:85178995320

SN - 0166-218X

VL - 345

SP - 141

EP - 146

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Properly colored cycles in edge-colored 2-colored-triangle-free complete graphs

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this