A new type of edge-derived vertex coloring

Ervin Gyori; Cory Palmer

doi:10.1016/j.disc.2008.11.014

A new type of edge-derived vertex coloring

Ervin Gyori
, Cory Palmer

Mathematical Sciences

Hungarian Academy of Sciences

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

9 Scopus citations

Abstract

We study the minimum number of weights assigned to the edges of a graph G with no component K₂ so that any two adjacent vertices have distinct sets of weights on their incident edges. The best possible upper bound on this parameter is proved.

Original language	English
Pages (from-to)	6344-6352
Number of pages	9
Journal	Discrete Mathematics
Volume	309
Issue number	22
DOIs	https://doi.org/10.1016/j.disc.2008.11.014
State	Published - Nov 28 2009

Funding

The authors would like to thank the anonymous referees for their careful reading of the manuscript for errors and for valuable suggestions for improving the presentation of several of the proofs. The first author was partially supported by the Hungarian OTKA Grant AT 48826 and by ToK project FIST of Rényi Institute in the 6th Framework Program of the European Union.

Funder number
AT 48826

Keywords

Chromatic number
Edge coloring
Edge-weighting

Access to Document

10.1016/j.disc.2008.11.014

Cite this

@article{5a649b7e55cd44a596cdcdeb63de3edf,

title = "A new type of edge-derived vertex coloring",

abstract = "We study the minimum number of weights assigned to the edges of a graph G with no component K2 so that any two adjacent vertices have distinct sets of weights on their incident edges. The best possible upper bound on this parameter is proved.",

keywords = "Chromatic number, Edge coloring, Edge-weighting",

author = "Ervin Gyori and Cory Palmer",

note = "Funding Information: The authors would like to thank the anonymous referees for their careful reading of the manuscript for errors and for valuable suggestions for improving the presentation of several of the proofs. The first author was partially supported by the Hungarian OTKA Grant AT 48826 and by ToK project FIST of R{\'e}nyi Institute in the 6th Framework Program of the European Union.",

year = "2009",

month = nov,

day = "28",

doi = "10.1016/j.disc.2008.11.014",

language = "English",

volume = "309",

pages = "6344--6352",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "22",

}

TY - JOUR

T1 - A new type of edge-derived vertex coloring

AU - Gyori, Ervin

AU - Palmer, Cory

N1 - Funding Information: The authors would like to thank the anonymous referees for their careful reading of the manuscript for errors and for valuable suggestions for improving the presentation of several of the proofs. The first author was partially supported by the Hungarian OTKA Grant AT 48826 and by ToK project FIST of Rényi Institute in the 6th Framework Program of the European Union.

PY - 2009/11/28

Y1 - 2009/11/28

N2 - We study the minimum number of weights assigned to the edges of a graph G with no component K2 so that any two adjacent vertices have distinct sets of weights on their incident edges. The best possible upper bound on this parameter is proved.

AB - We study the minimum number of weights assigned to the edges of a graph G with no component K2 so that any two adjacent vertices have distinct sets of weights on their incident edges. The best possible upper bound on this parameter is proved.

KW - Chromatic number

KW - Edge coloring

KW - Edge-weighting

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

U2 - 10.1016/j.disc.2008.11.014

DO - 10.1016/j.disc.2008.11.014

M3 - Article

AN - SCOPUS:70350569322

SN - 0012-365X

VL - 309

SP - 6344

EP - 6352

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 22

ER -

A new type of edge-derived vertex coloring

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this