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

Khachatrian Hrant

Ամփոփում:

An edge‐coloring of a graph G with colors urn:x-wiley:03649024:media:jgt21759:jgt21759-math-0001 is called an interval t‐coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erdős constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erdős's counterexample is the smallest (in a sense of maximum degree) known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non‐edge‐colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.

Հրատարակիչ:

Elsevier

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

17.01.2013

Թողարկման ամսաթիվը:

22.05.2013

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

21.08.2014

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

oai:noad.sci.am:136138

DOI:

10.1002/jgt.21759

ISSN:

0364-9024

Լեզու:

English

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

Graph Theory

Հատոր:

76

Համար:

3

URL:

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

pet_petros@ipia.sci.am ; hrant@egern.net

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

Institute for Informatics and Automation Problems ; Yerevan State University ; Department of informatics and applied mathematics

Երկիր:

Armenia

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

WOS