Geodesic
On improper interval edge colourings
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 4, pp. 1119-1128
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-016-0313-7
Classification : 05C15
Keywords: edge colouring; interval colouring; improper colouring 
@article{10_1007_s10587_016_0313_7,
     author = {Hud\'ak, Peter and Kardo\v{s}, Franti\v{s}ek and Madaras, Tom\'a\v{s} and Vrbjarov\'a, Michaela},
     title = {On improper interval edge colourings},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1119--1128},
     year = {2016},
     volume = {66},
     number = {4},
     doi = {10.1007/s10587-016-0313-7},
     mrnumber = {3572926},
     zbl = {06674865},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0313-7/}
}
TY  - JOUR
AU  - Hudák, Peter
AU  - Kardoš, František
AU  - Madaras, Tomáš
AU  - Vrbjarová, Michaela
TI  - On improper interval edge colourings
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 1119
EP  - 1128
VL  - 66
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0313-7/
DO  - 10.1007/s10587-016-0313-7
LA  - en
ID  - 10_1007_s10587_016_0313_7
ER  - 
%0 Journal Article
%A Hudák, Peter
%A Kardoš, František
%A Madaras, Tomáš
%A Vrbjarová, Michaela
%T On improper interval edge colourings
%J Czechoslovak Mathematical Journal
%D 2016
%P 1119-1128
%V 66
%N 4
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0313-7/
%R 10.1007/s10587-016-0313-7
%G en
%F 10_1007_s10587_016_0313_7
Hudák, Peter; Kardoš, František; Madaras, Tomáš; Vrbjarová, Michaela. On improper interval edge colourings. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 4, pp. 1119-1128. doi: 10.1007/s10587-016-0313-7

[1] Asratian, A. S., Kamalian, R. R.: Investigation of interval edge-colorings of graphs. J. Comb. Theory, Ser. B 62 (1994), 34-43. | DOI | MR

[2] Asratyan, A. S., Kamalyan, R. R.: Interval colorings of edges of a multigraph. Prikl. Mat. Erevan Russian 5 (1987), 25-34. | MR | Zbl

[3] Axenovich, M. A.: On interval colorings of planar graphs. Congr. Numerantium 159 (2002), 77-94. | MR | Zbl

[4] Diestel, R.: Graph Theory. Graduate Texts in Mathematics 173 Springer, Berlin (2006). | MR | Zbl

[5] Giaro, K.: The complexity of consecutive $\Delta$-coloring of bipartite graphs: 4 is easy, 5 is hard. Ars Comb. 47 (1997), 287-298. | MR | Zbl

[6] Giaro, K., Kubale, M., Małafiejski, M.: On the deficiency of bipartite graphs. Discrete Appl. Math. 94 (1999), 193-203. | DOI | MR | Zbl

[7] Giaro, K., Kubale, M., Małafiejski, M.: Consecutive colorings of the edges of general graphs. Discrete Math. 236 (2001), 131-143. | DOI | MR | Zbl

[8] Janczewski, R., Małafiejska, A., Małafiejski, M.: Interval incidence graph coloring. Discrete Appl. Math. 182 (2015), 73-83. | DOI | MR | Zbl

[9] Khachatrian, H. H., Petrosyan, P. A.: Interval edge-colorings of complete graphs. (2014), 18 pages. Available at arXiv:1411.5661 [cs.DM]. | MR

[10] Petrosyan, P. A.: Interval edge-colorings of complete graphs and $n$-dimensional cubes. Discrete Math. 310 (2010), 1580-1587. | DOI | MR | Zbl

[11] Sevast'yanov, S. V.: Interval colorability of the edges of a bipartite graph. Metody Diskret. Analiz. 50 (1990), 61-72 Russian. | MR

Cité par Sources :