| Title:
|
On improper interval edge colourings (English) |
| Author:
|
Hudák, Peter |
| Author:
|
Kardoš, František |
| Author:
|
Madaras, Tomáš |
| Author:
|
Vrbjarová, Michaela |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
4 |
| Year:
|
2016 |
| Pages:
|
1119-1128 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
edge colouring |
| Keyword:
|
interval colouring |
| Keyword:
|
improper colouring |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 06674865 |
| idMR:
|
MR3572926 |
| DOI:
|
10.1007/s10587-016-0313-7 |
| . |
| Date available:
|
2016-11-26T20:53:32Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145922 |
| . |
| Reference:
|
[1] Asratian, A. S., Kamalian, R. R.: Investigation of interval edge-colorings of graphs.J. Comb. Theory, Ser. B 62 (1994), 34-43. MR 1290629, 10.1006/jctb.1994.1053 |
| Reference:
|
[2] Asratyan, A. S., Kamalyan, R. R.: Interval colorings of edges of a multigraph.Prikl. Mat. Erevan Russian 5 (1987), 25-34. Zbl 0742.05038, MR 1003403 |
| Reference:
|
[3] Axenovich, M. A.: On interval colorings of planar graphs.Congr. Numerantium 159 (2002), 77-94. Zbl 1026.05036, MR 1985168 |
| Reference:
|
[4] Diestel, R.: Graph Theory.Graduate Texts in Mathematics 173 Springer, Berlin (2006). Zbl 1093.05001, MR 2159259 |
| Reference:
|
[5] Giaro, K.: The complexity of consecutive $\Delta$-coloring of bipartite graphs: 4 is easy, 5 is hard.Ars Comb. 47 (1997), 287-298. Zbl 0933.05050, MR 1487186 |
| Reference:
|
[6] Giaro, K., Kubale, M., Małafiejski, M.: On the deficiency of bipartite graphs.Discrete Appl. Math. 94 (1999), 193-203. Zbl 0933.05054, MR 1682166, 10.1016/S0166-218X(99)00021-9 |
| Reference:
|
[7] Giaro, K., Kubale, M., Małafiejski, M.: Consecutive colorings of the edges of general graphs.Discrete Math. 236 (2001), 131-143. Zbl 1007.05045, MR 1830605, 10.1016/S0012-365X(00)00437-4 |
| Reference:
|
[8] Janczewski, R., Małafiejska, A., Małafiejski, M.: Interval incidence graph coloring.Discrete Appl. Math. 182 (2015), 73-83. Zbl 1306.05062, MR 3301936, 10.1016/j.dam.2014.03.006 |
| Reference:
|
[9] Khachatrian, H. H., Petrosyan, P. A.: Interval edge-colorings of complete graphs. (2014), 18 pages.Available at arXiv:1411.5661 [cs.DM]. MR 3512339 |
| Reference:
|
[10] Petrosyan, P. A.: Interval edge-colorings of complete graphs and $n$-dimensional cubes.Discrete Math. 310 (2010), 1580-1587. Zbl 1210.05048, MR 2601268, 10.1016/j.disc.2010.02.001 |
| Reference:
|
[11] Sevast'yanov, S. V.: Interval colorability of the edges of a bipartite graph.Metody Diskret. Analiz. 50 (1990), 61-72 Russian. MR 1173570 |
| . |
