Օբյեկտ

Վերնագիր: On sum edge-coloring of regular, bipartite and split graphs

Հեղինակ:

Petrosyan Petros

Տեսակ:

Article

Համահեղինակ(ներ):

Kamalian Rafayel Ruben

Ամփոփում:

An edge-coloring of a graph G with natural numbers is called a sum edge-coloring if the colors of edges incident to any vertex of G are distinct and the sum of the colors of the edges of G is minimum. The edge-chromatic sum of a graph G is the sum of the colors of edges in a sum edge-coloring of G. It is known that the problem of finding the edge-chromatic sum of an r-regular (r≥3) graph is NP-complete. In this paper we give a polynomial time (1+2r(r+1)2)-approximation algorithm for the edge-chromatic sum problem on r-regular graphs for r≥3. Also, it is known that the problem of finding the edge-chromatic sum of bipartite graphs with maximum degree 3 is NP-complete. We show that the problem remains NP-complete even for some restricted class of bipartite graphs with maximum degree 3. Finally, we give upper bounds for the edge-chromatic sum of some split graphs.

Հրատարակիչ:

Elsevier

Հանձնման ամսաթիվը:

30.11.2011

Ընդունման ամսաթիվը:

27.09.2013

Հրատարակման ամսաթիվ:

21.10.2013

Նույնականացուցիչ:

oai:noad.sci.am:136141

DOI:

10.1016/j.dam.2013.09.025

ISSN:

0166-218X

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Discrete Applied Mathematics

Հատոր:

165

URL:


Կազմակերպության անվանում:

Institute for Informatics and Automation Problems ; Russian-Armenian State University ; Department of Applied Mathematics and Informatics

Երկիր:

Armenia

Ինդեքսավորում:

WOS

Օբյեկտի հավաքածուներ:

Վերջին անգամ ձևափոխված:

Apr 19, 2021

Մեր գրադարանում է սկսած:

Apr 19, 2021

Օբյեկտի բովանդակության հարվածների քանակ:

23

Օբյեկտի բոլոր հասանելի տարբերակները:

https://noad.sci.am/publication/149562

Ցույց տալ նկարագրությունը RDF ձևաչափով:

RDF

Ցույց տալ նկարագրությունը OAI-PMH ձևաչափով։

OAI-PMH

Հրատարակության անուն Ամսաթիվ
Petros Petrosyan, On sum edge-coloring of regular, bipartite and split graphs Apr 19, 2021

Այս էջը օգտագործում է 'cookie-ներ'։ Ավելի տեղեկատվություն