Discussiones Mathematicae Graph Theory 29(1) (2009)
143-162
doi: 10.7151/dmgt.1437
Hajo Broersma^{1}, Bert Marchal^{2}, Daniel Paulusma^{1} and A.N.M. Salman^{3}
^{1}Department of Computer Science
Durham University, Science Laboratories
South Road, Durham DH1 3LE, England
e-mail: {hajo.broersma,daniel.paulusma}@durham.ac.uk
^{2}Faculty of Economics and Business Administration
Department of Quantitative Economics, University of Maastricht
P.O. Box 616, 6200 MD Maastricht, The Netherlands
e-mail: b.marchal@ke.unimaas.nl
^{3}Faculty of Mathematics and Natural Sciences
Institut Teknologi Bandung
Jalan Ganesa 10, Bandung 40132, Indonesia
e-mail: msalman@math.itb.ac.id
Keywords: backbone coloring, split graph, matching, star.
2000 Mathematics Subject Classification: 05C15, 015C85, 015C17.
[1] | J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976). |
[2] | H.J. Broersma, A general framework for coloring problems: old results, new results and open problems, in: Proceedings of IJCCGGT 2003, LNCS 3330 (2005) 65-79. |
[3] | H.J. Broersma, F.V. Fomin, P.A. Golovach and G.J. Woeginger, Backbone colorings for networks, in: Proceedings of WG 2003, LNCS 2880 (2003) 131-142. |
[4] | H.J. Broersma, F.V. Fomin, P.A. Golovach and G.J. Woeginger, Backbone colorings for graphs: tree and path backbones, J. Graph Theory 55 (2007) 137-152, doi: 10.1002/jgt.20228. |
[5] | H.J. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A.N.M. Salman and K. Yoshimoto, λ-Backbone colorings along pairwise disjoint stars and matchings, preprint (2004).
www.durham.ac.uk/daniel.paulusma/Publications/Papers/ Submitted/backbone.pdf |
[6] | H.J. Broersma, L. Marchal, D. Paulusma and A.N.M. Salman, Improved upper bounds for λ-backbone colorings along matchings and stars, in: Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2007, LNCS 4362 (2007) 188-199. |
[7] | M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). |
[8] | P.L. Hammer and S. Földes, Split graphs, Congr. Numer. 19 (1977) 311-315. |
Received 17 December 2007
Accepted 23 October 2008