The deficiency of all generalized Hertz graphs and minimal consecutively non-colourable graphs in this class
详细信息 查看全文
- 作者：Marta Borowiecka-Olszewska M.Borowiecka-Olszewska@wmie.uz.zgora.pl" class="auth_mail" title="E-mail the corresponding author ; Ewa Drgas-Burchardt ; E.Drgas-Burchardt@wmie.uz.zgora.pl" class="auth_mail" title="E-mail the corresponding author
- 关键词：Edge colouring ; Consecutive (interval) colouring ; Deficiency
- 刊名：Discrete Mathematics
- 出版年：2016
- 出版时间：6 July 2016
- 年：2016
- 卷：339
- 期：7
- 页码：1892-1908
- 全文大小：483 K
文摘
A proper edge colouring of a graph with natural numbers is consecutive if colours of edges incident with each vertex form an interval of integers. The deficiency 
of a graph G is the minimum number of pendant edges whose attachment to G makes it consecutively colourable. In 1999 Giaro, Kubale and Małafiejski considered the deficiency of the Hertz graphs. In this paper we study the deficiency of graphs from much wider class, which we call the generalized Hertz graphs. We find the exact values of the deficiency of all graphs from this class. Our investigation confirms, in this class, the conjecture that the deficiency of an arbitrary graph is not greater than its order. Moreover, we describe necessary and sufficient conditions which guarantee that the generalized Hertz graph is consecutively colourable, and necessary and sufficient conditions which guarantee that such a graph is minimal consecutively non-colourable. Applying the last mentioned result, we give the generating function for the sequence whose specified elements represent numbers of the minimal generalized Hertz graphs that are not consecutively colourable. One can find (Petrosyan and Khachatrian, 2014) the sufficient condition for consecutive non-colourability of bipartite graphs constructed based on trees in which any two leaves are in an even distance. In the paper we show that the same condition is also necessary for generalized Hertz graphs.
of a graph G is the minimum number of pendant edges whose attachment to G makes it consecutively colourable. In 1999 Giaro, Kubale and Małafiejski considered the deficiency of the Hertz graphs. In this paper we study the deficiency of graphs from much wider class, which we call the generalized Hertz graphs. We find the exact values of the deficiency of all graphs from this class. Our investigation confirms, in this class, the conjecture that the deficiency of an arbitrary graph is not greater than its order. Moreover, we describe necessary and sufficient conditions which guarantee that the generalized Hertz graph is consecutively colourable, and necessary and sufficient conditions which guarantee that such a graph is minimal consecutively non-colourable. Applying the last mentioned result, we give the generating function for the sequence whose specified elements represent numbers of the minimal generalized Hertz graphs that are not consecutively colourable. One can find (Petrosyan and Khachatrian, 2014) the sufficient condition for consecutive non-colourability of bipartite graphs constructed based on trees in which any two leaves are in an even distance. In the paper we show that the same condition is also necessary for generalized Hertz graphs.