Օբյեկտ

Վերնագիր: Interval edge-colorings of complete graphs

Հեղինակ:

Khachatrian Hrant

Տեսակ:

Article

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

Petrosyan Petros

Ամփոփում:

An edge-coloring of a graph G with colors 1,2,…,t is an interval t-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. For an interval colorable graph G, W(G) denotes the greatest value of t for which G has an interval t-coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of W(K2n) is known only for n≤4. The second author showed that if n=p2q, where p is odd and q is nonnegative, then W(K2n)≥4n−2−p−q. Later, he conjectured that if n∈N, then W(K2n)=4n−2−⌊log2n⌋−‖n2‖, where ‖n2‖ is the number of 1’s in the binary representation of n. In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on W(K2n) and determine its exact values for n≤12.

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

20.11.2014

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

02.04.2016

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

06.05.2016

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

oai:noad.sci.am:136137

DOI:

10.1016/j.disc.2016.04.002

ISSN:

0012-365X

Լեզու:

English

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

Discrete Mathematics

Հատոր:

339

Համար:

9

URL:


լրացուցիչ տեղեկատվություն:

hrant.khachatrian@ysu.am ; pet_petros@ipia.sci.am

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

Yerevan State University ; Institute for Informatics and Automation Problems

Երկիր:

Armenia

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

WOS

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

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

Apr 19, 2021

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

Apr 19, 2021

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

12

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

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

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

RDF

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

OAI-PMH

Հրատարակության անուն Ամսաթիվ
Hrant Khachatrian, Interval edge-colorings of complete graphs Apr 19, 2021

Օբյեկտներ

Նման

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