On improper interval edge colourings

Czechoslovak Mathematical Journal

Peter Hudák¹  František Kardoš²  Tomáš ³ 

[1] Institute of Mathematics, Faculty of Sciences, University of P. J. Šafárik, Jesenná 5, 040 01 Košice, Slovak Republic;LaBRI, University of Bordeaux, 351, cours de la Libération, 33405 Talence, France;Michaela Vrbjarová, Institute of Mathematics, Faculty of Sciences, University of P. J. Šafárik, Jesenná 5, 040 01 Košice, Slovak Republic

关键词: edge colouring;    interval colouring;    improper colouring;   

DOI  :  

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

We study improper interval edge colourings, defined by the requirement that the edge colours around each vertex form an integer interval. For the corresponding chromatic invariant (being the maximum number of colours in such a colouring), we present upper and lower bounds and discuss their qualities; also, we determine its values and estimates for graphs of various families, like wheels, prisms or complete graphs. The study of this parameter was inspired by the interval colouring, introduced by Asratian, Kamalian (1987). The difference is that we relax the requirement on the original colouring to be proper.

【 授权许可】

Unknown