On backbone colorings with galaxy backbones

• Julio Araujo UFC
• Alexandre Cezar UFC
• Rayane Castro UFC

DOI: https://doi.org/10.5753/etc.2022.223114

Abstract

Given an integer q ≥ 2, a simple graph G and a spanning subgraph H, the (circular) q-backbone chromatic number, BBCq(G, H) (resp. CBCq(G, H)) is the smallest integer k such that G has a proper k-coloring f satisfying that if uv ∈ E(H), then |f(u)−f(v)| ≥ q (resp. k−q ≥ |f(u)−f(v)| ≥ q). In this work, we show that for a given planar graph G and a matching M, it holds that CBCq(G, M) ≤ q + 5, for q ∈ {2, 3}, without using the Four Color Theorem. Furthermore, we fix a lemma presented by Havet, King, Liedloff & Todinca (2014).

Keywords: bounds, matching, circular backbone coloring

References

C. Araujo, J. Araujo, A. Silva, and A. Cezar, Backbone coloring of graphs with galaxy backbones, Electronic Notes in Theoretical Computer 346 (2019), 43–64.

H. Broersma, F. V. Fomin, P. A. Golovach, and G. J. Woeginger, Backbone colorings for networks, International Workshop on Graph-Theoretic Concepts in Computer Science, 2003, pp. 131–142.

H. Broersma, F. V. Fomin, G. J. Woeginger, and P. A. Golovach, Backbone colorings for graphs: tree and path backbones, Journal of Graph Theory 55 (2007), no. 2, 137–152.

H. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A. N. M. Salman, and K. Yoshimoto, λ-backbone colorings along pairwise disjoint stars and matchings, Discrete Mathematics 309 (2009), no. 18, 5596– 5609. Combinatorics 2006, A Meeting in Celebration of Pavol Hell’s 60th Birthday (May 1–5, 2006).

H. Broersma, J. Fujisawa, and K. Yoshimoto, Backbone colorings along perfect matchings, Memorandum, University of Twente, Department of Applied Mathematics, 2003 (English).

M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of np-completeness (series of books in the mathematical sciences), First Edition, W. H. Freeman, 1979.

W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE 68 (1980), no. 12, 1497–1514.

F. Havet, A. D. King, M. Liedloff, and I. Todinca, (circular) backbone colouring: Forest backbones in planar graphs, Discrete Applied Mathematics 169 (2014), 119–134.

D. B. West, Introduction to graph theory, 2nd ed., Prentice Hall, 2001.