Geodesic
Forbidden Structures for Planar Perfect Consecutively Colourable Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 315-336.

Voir la notice de l'article provenant de la source Library of Science

A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced subgraphs are consecutively colourable, too. We call elements of this class perfect consecutively colourable to emphasise the conceptual similarity to perfect graphs. Obviously, the class of perfect consecutively colourable graphs is induced hereditary, so it can be characterized by the family of induced forbidden graphs. In this work we give a necessary and sufficient conditions that must be satisfied by the generalized Sevastjanov rosette to be an induced forbid- den graph for the class of perfect consecutively colourable graphs. Along the way, we show the exact values of the deficiency of all generalized Sevastjanov rosettes, which improves the earlier known estimating result. It should be mentioned that the deficiency of a graph measures its closeness to the class of consecutively colourable graphs. We motivate the investigation of graphs considered here by showing their connection to the class of planar perfect consecutively colourable graphs.
Keywords: edge colouring, consecutive (interval) colouring, deficiency, Sevastjanov graph, forbidden graph 
@article{DMGT_2017_37_2_a1,
     author = {Borowiecka-Olszewska, Marta and Drgas-Burchardt, Ewa},
     title = {Forbidden {Structures} for {Planar} {Perfect} {Consecutively} {Colourable} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {315--336},
     publisher = {mathdoc},
     volume = {37},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a1/}
}
TY  - JOUR
AU  - Borowiecka-Olszewska, Marta
AU  - Drgas-Burchardt, Ewa
TI  - Forbidden Structures for Planar Perfect Consecutively Colourable Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 315
EP  - 336
VL  - 37
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a1/
LA  - en
ID  - DMGT_2017_37_2_a1
ER  - 
%0 Journal Article
%A Borowiecka-Olszewska, Marta
%A Drgas-Burchardt, Ewa
%T Forbidden Structures for Planar Perfect Consecutively Colourable Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 315-336
%V 37
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a1/
%G en
%F DMGT_2017_37_2_a1
Borowiecka-Olszewska, Marta; Drgas-Burchardt, Ewa. Forbidden Structures for Planar Perfect Consecutively Colourable Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 315-336. http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a1/

[1] A.S. Asratian and C.J. Casselgren, On interval edge colorings of (α,ß)-biregular bipartite graphs, Discrete Math. 307 (2006) 1951-1956. doi: 10.1016/j.disc.2006.11.001

[2] A.S. Asratian and R.R. Kamalian, Interval colorings of the edges of multigraph, Appl. Math. 5 (1987) 25-34, in Russian.

[3] A.S. Asratian and R.R. Kamalian, Investigation on interval edge-colorings of graphs, J. Combin. Theory Ser. B 62 (1994) 34-43. doi: 10.1006/jctb.1994.1053

[4] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002) 77-94.

[5] M. Borowiecka-Olszewska, E. Drgas-Burchardt and M. Ha luszczak, On the structure and deficiency of k-trees with bounded degree, Discrete Appl. Math. 201 (2016) 24-37. doi: 10.1016/j.dam.2015.08.008

[6] M. Borowiecka-Olszewska and E. Drgas-Burchardt, The deficiency of all generalized Hertz graphs and minimal consecutively non-colourable graphs in this class, Discrete Math. 339 (2016) 1892-1908. doi: 10.1016/j.disc.2015.12.028

[7] R. Diestel, Graph Theory, 2nd ed. (Graduate Texts in Mathematics 173, Springer-Verlag, New York, 2000).

[8] K. Giaro, The complexity of consecutive ∆-coloring of bipartite graphs: 4 is easy, 5 is hard, Ars Combin. 47 (1997) 287-300.

[9] K. Giaro and M. Kubale, Consecutive edge-colorings of complete and incomplete Cartesian products of graphs, Congr. Numer. 128 (1997) 143-149.

[10] K. Giaro and M. Kubale, Compact scheduling of zero-one time operations in multi-stage systems, Discrete Appl. Math. 145 (2004) 95-103. doi: 0.1016/j.dam.2003.09.010

[11] K. Giaro, M. Kubale and M. Ma lafiejski, On the deficiency of bipartite graphs, Discrete Appl. Math. 94 (1999) 193-203. doi: 10.1016/S0166-218X(99)00021-9

[12] D.L. Greenwell, R.L. Hemminger and J. Klerlein, Forbidden subgraphs, in: Proc. Of the 4th S-E Conf. Combinatorics, Graph Theory and Computing (Utilitas Math., Winnipeg, Man. 1973) 389-394.

[13] D. Hanson and C.O.M. Loten, A lower bound for interval colouring of bi-regular bipartite graphs, Bull. Inst. Comb. Appl. 18 (1996) 69-74.

[14] D. Hanson, C.O.M. Loten and B. Toft, On interval colorings of bi-regular bipartite graphs, Ars Combin. 50 (1998) 23-32.

[15] R.R. Kamalian, Interval Coloring of Complete Bipartite Graphs and Trees (in Russian) (Preprint of Comp. Cen. of Acad. Sci. of Armenian SSR, Erevan, 1989).

[16] M. Kubale, Graph Colorings (American Mathematical Society, Providence, Rhode Island, 2004). doi: 10.1090/conm/352

[17] P.A. Petrosyan, Interval edge-colorings of complete graphs and n-dimensional cubes, Discrete Math. 310 (2010) 1580-1587. doi: 10.1016/j.disc.2010.02.001

[18] P.A. Petrosyan, Interval edge colorings of some products of graphs, Discuss. Math. Graph Theory 31 (2011) 357-373. doi: 10.7151/dmgt.1551

[19] P.A. Petrosyan, H.H. Khachatrian and H.G. Tananyan, Interval edge-colorings of Cartesian products of graphs I, Discuss. Math. Graph Theory 33 (2013) 613-632. doi: 10.7151/dmgt.1693

[20] P.A. Petrosyan and H.H. Khachatrian, Interval non-edge-colorable bipartite graphs and multigraphs, J. Graph Theory 76 (2014) 200-216. doi: 10.1002/jgt.21759

[21] A.V. Pyatkin, Interval coloring of (3, 4)-biregular bipartite graphs having large cubic subgraphs, J. Graph Theory 47 (2004) 122-128. doi: 0.1002/jgt.20021

[22] S.V. Sevastjanov, On interval colorability of bipartite graphs, Met. Diskret Analiz. 50 (1990) 61-72, in Russian.