Colorações backbone em grafos com galáxias backbone

Abstract

A (proper) k-coloring of a graph G is a function φ: V (G) → {1, . . . , k} such that φ(u) ̸= φ(v), for all edge uv ∈ E(G). Given a graph G and a subgraph H ⊆ G, a q-backbone k-coloring of (G, H) is a k-coloring of G such that |φ(u)−φ(v)| ≥ q, for all edge uv ∈ E(H). The q-backbone chromatic number of (G, H), denoted by BBC q (G, H), is the smallest k ∈ Z such that there exists a q-backbone k-coloring of (G, H). A circular q-backbone k-coloring of (G, H) is a k-coloring of G such that q ≤ |φ(u) − φ(v)| ≤ k − q, for all edge uv ∈ E(H). The circular q-backbone chromatic number of (G, H), denoted by CBC q (G, H), is the smallest k ∈ Z such that there exists a circular q-backbone k-coloring of (G, H). In this dissertation, in addition to a brief presentation of the results related to Backbone Coloring, we present our contributions, among which we partially answer three problems proposed in (Havet, Frédéric et al., 2014): we show that if G is a planar graph with a spanning subgraph H, then CBC q (G, H) ≤ 2q + 2 when q ≥ 3 and H is a galaxy; CBC q (G, H) ≤ 2q when q ≥ 4 and H is a matching; and, CBC 3 (G, H) ≤ 7 when G does not have a pair of triangles with adjacent edges and H is a matching. Some of these results follow as a consequence of more general results we obtained about the parameter CBC q (G, H) for graph classes larger than the class of planar graphs. In addition, we show that it is possible to determine BBC q (G, H) and CBC q (G, H) in polynomial time when G has bounded treewidth graph and H is a matching of G. Finally, we present an error in the demonstration that BBC 2 (G, H) ≤ ∆(G) + 1, for any matching H in an arbitrary graph G (Miskuf, Jozef et al., 2010), and we present a demonstration for this result.