A classification of edge-colored graphs based on properly colored walks

Ruonan Li; Binlong Li; Shenggui Zhang

doi:10.1016/j.dam.2020.02.008

A classification of edge-colored graphs based on properly colored walks

Ruonan Li
, Binlong Li
, Shenggui Zhang

School of Mathematics and Statistics

Northwestern Polytechnical University Xian

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

A properly colored walk in an edge-colored graph is a walk such that consecutive edges are of distinct colors. In this paper, based on a transformation from directed graphs to edge-colored graphs, we classified edge-colored graphs into three families: degenerate edge-colored graphs, semi-degenerate edge-colored graphs and non-degenerate graphs. By a polynomial-time computable parameter related to properly colored walks, we gave a characterization of these three families. Applying this characterization, we slightly strengthened Yeo's Theorem (Every edge-colored graph G containing no PC cycle contains a vertex z∈V(G) such that each component of G−z is joint to z with at most one color, Yeo, 1997).

Original language	English
Pages (from-to)	590-595
Number of pages	6
Journal	Discrete Applied Mathematics
Volume	283
DOIs	https://doi.org/10.1016/j.dam.2020.02.008
State	Published - 15 Sep 2020

Keywords

Cycles
Digraphs
Edge-colored graphs
Properly colored
Walks

Access to Document

10.1016/j.dam.2020.02.008

Cite this

@article{a9f9310564a74e06b3200044f3cbbf75,

title = "A classification of edge-colored graphs based on properly colored walks",

abstract = "A properly colored walk in an edge-colored graph is a walk such that consecutive edges are of distinct colors. In this paper, based on a transformation from directed graphs to edge-colored graphs, we classified edge-colored graphs into three families: degenerate edge-colored graphs, semi-degenerate edge-colored graphs and non-degenerate graphs. By a polynomial-time computable parameter related to properly colored walks, we gave a characterization of these three families. Applying this characterization, we slightly strengthened Yeo's Theorem (Every edge-colored graph G containing no PC cycle contains a vertex z∈V(G) such that each component of G−z is joint to z with at most one color, Yeo, 1997).",

keywords = "Cycles, Digraphs, Edge-colored graphs, Properly colored, Walks",

author = "Ruonan Li and Binlong Li and Shenggui Zhang",

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

year = "2020",

month = sep,

day = "15",

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

language = "英语",

volume = "283",

pages = "590--595",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A classification of edge-colored graphs based on properly colored walks

AU - Li, Ruonan

AU - Li, Binlong

AU - Zhang, Shenggui

PY - 2020/9/15

Y1 - 2020/9/15

N2 - A properly colored walk in an edge-colored graph is a walk such that consecutive edges are of distinct colors. In this paper, based on a transformation from directed graphs to edge-colored graphs, we classified edge-colored graphs into three families: degenerate edge-colored graphs, semi-degenerate edge-colored graphs and non-degenerate graphs. By a polynomial-time computable parameter related to properly colored walks, we gave a characterization of these three families. Applying this characterization, we slightly strengthened Yeo's Theorem (Every edge-colored graph G containing no PC cycle contains a vertex z∈V(G) such that each component of G−z is joint to z with at most one color, Yeo, 1997).

AB - A properly colored walk in an edge-colored graph is a walk such that consecutive edges are of distinct colors. In this paper, based on a transformation from directed graphs to edge-colored graphs, we classified edge-colored graphs into three families: degenerate edge-colored graphs, semi-degenerate edge-colored graphs and non-degenerate graphs. By a polynomial-time computable parameter related to properly colored walks, we gave a characterization of these three families. Applying this characterization, we slightly strengthened Yeo's Theorem (Every edge-colored graph G containing no PC cycle contains a vertex z∈V(G) such that each component of G−z is joint to z with at most one color, Yeo, 1997).

KW - Cycles

KW - Digraphs

KW - Edge-colored graphs

KW - Properly colored

KW - Walks

UR - https://www.scopus.com/pages/publications/85080024876

U2 - 10.1016/j.dam.2020.02.008

DO - 10.1016/j.dam.2020.02.008

M3 - 文章

AN - SCOPUS:85080024876

SN - 0166-218X

VL - 283

SP - 590

EP - 595

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

A classification of edge-colored graphs based on properly colored walks

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this