On improper interval edge colourings

Peter Hudák; František Kardoš; Tomáš Madaras; Michaela Vrbjarová

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 4, page 1119-1128
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Hudák, Peter, et al. "On improper interval edge colourings." Czechoslovak Mathematical Journal 66.4 (2016): 1119-1128. <http://eudml.org/doc/287575>.

@article{Hudák2016,
abstract = {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.},
author = {Hudák, Peter, Kardoš, František, Madaras, Tomáš, Vrbjarová, Michaela},
journal = {Czechoslovak Mathematical Journal},
keywords = {edge colouring; interval colouring; improper colouring; edge colouring; interval colouring; improper colouring},
language = {eng},
number = {4},
pages = {1119-1128},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On improper interval edge colourings},
url = {http://eudml.org/doc/287575},
volume = {66},
year = {2016},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 4
SP - 1119
EP - 1128
AB - 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.
LA - eng
KW - edge colouring; interval colouring; improper colouring; edge colouring; interval colouring; improper colouring
UR - http://eudml.org/doc/287575
ER -

References

top
  1. Asratian, A. S., Kamalian, R. R., 10.1006/jctb.1994.1053, J. Comb. Theory, Ser. B 62 (1994), 34-43. (1994) MR1290629DOI10.1006/jctb.1994.1053
  2. Asratyan, A. S., Kamalyan, R. R., Interval colorings of edges of a multigraph, Prikl. Mat. Erevan Russian 5 (1987), 25-34. (1987) Zbl0742.05038MR1003403
  3. Axenovich, M. A., On interval colorings of planar graphs, Congr. Numerantium 159 (2002), 77-94. (2002) Zbl1026.05036MR1985168
  4. Diestel, R., Graph Theory, Graduate Texts in Mathematics 173 Springer, Berlin (2006). (2006) Zbl1093.05001MR2159259
  5. Giaro, K., The complexity of consecutive Δ -coloring of bipartite graphs: 4 is easy, 5 is hard, Ars Comb. 47 (1997), 287-298. (1997) Zbl0933.05050MR1487186
  6. Giaro, K., Kubale, M., Małafiejski, M., 10.1016/S0166-218X(99)00021-9, Discrete Appl. Math. 94 (1999), 193-203. (1999) Zbl0933.05054MR1682166DOI10.1016/S0166-218X(99)00021-9
  7. Giaro, K., Kubale, M., Małafiejski, M., 10.1016/S0012-365X(00)00437-4, Discrete Math. 236 (2001), 131-143. (2001) Zbl1007.05045MR1830605DOI10.1016/S0012-365X(00)00437-4
  8. Janczewski, R., Małafiejska, A., Małafiejski, M., 10.1016/j.dam.2014.03.006, Discrete Appl. Math. 182 (2015), 73-83. (2015) Zbl1306.05062MR3301936DOI10.1016/j.dam.2014.03.006
  9. Khachatrian, H. H., Petrosyan, P. A., Interval edge-colorings of complete graphs. (2014), 18 pages, Available at arXiv:1411.5661 [cs.DM]. MR3512339
  10. Petrosyan, P. A., 10.1016/j.disc.2010.02.001, Discrete Math. 310 (2010), 1580-1587. (2010) Zbl1210.05048MR2601268DOI10.1016/j.disc.2010.02.001
  11. Sevast'yanov, S. V., Interval colorability of the edges of a bipartite graph, Metody Diskret. Analiz. 50 (1990), 61-72 Russian. (1990) MR1173570

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.