×

Optimal backbone coloring of split graphs with matching backbones. (English) Zbl 1307.05078

Summary: For a graph \(G\) with a given subgraph \(H\), the backbone coloring is defined as the mapping \(c : V (G) \to \mathbb N_+\) such that \(|c(u) - c(v)| \geq 2\) for each edge \(\{u, v\} \in E(H)\) and \(|c(u) - c(v)| \geq 1\) for each edge \(\{u, v\} \in E(G)\). The backbone chromatic number \(\operatorname{BBC}(G,H)\) is the smallest integer \(k\) such that there exists a backbone coloring with \(\max_{v\in V (G)} c(v) = k\).
In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.

MSC:

05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Hammer and S. Földes, Split graphs, Congr. Numer. XIX (1977) 311-315.; · Zbl 0407.05071
[2] J. Miškuf, R. Skrekovski and M. Tancer, Backbone colorings of graphs with bounded degree, Discrete Appl. Math. 158 (2010) 534-542. doi:10.1016/j.dam.2009.11.015; · Zbl 1215.05071
[3] H. 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; · Zbl 1118.05031
[4] H. Broersma, A general framework for coloring problems: old results, new results, and open problems, in: Combinatorial Geometry and Graph Theory: Indonesia- Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, J. Akiyama, E.T. Baskoro, M. Kano (Ed(s)), (Springer, 2003) 65-79.;
[5] R. Janczewski, On an interrelation between travelling salesman problem and T- coloring of graphs, Proceedings of the Sixth International Conference: Advanced Computer Systems, ACS 1999, Szczecin, Poland (1999) 23-25.;
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.