Steinberg-like theorems for backbone colouring

Julio Araujo 1 Frédéric Havet 2 Mathieu Schmitt 3
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : A function f:V(G)→{1,…,k}f:V(G)→{1,…,k} is a (proper) k-colouring of G if |f(u)−f(v)|≥1|f(u)−f(v)|≥1, for every edge uv∈E(G)uv∈E(G). The chromatic number χ(G)χ(G) is the smallest integer k for which there exists a proper k-colouring of G. Given a graph G and a subgraph H of G, a circular q-backbone k-colouring c of (G, H) is a k-colouring of G such that q≤|c(u)−c(v)|≤k−qq≤|c(u)−c(v)|≤k−q, for each edge uv∈E(H)uv∈E(H). The circular q-backbone chromatic number of a graph pair (G, H ), denoted CBCq(G,H)CBCq(G,H), is the minimum k such that (G, H) admits a circular q-backbone k-colouring. In this work, we first show that if G is a planar graph containing no cycle on 4 or 5 vertices and H⊆GH⊆G is a forest, then CBC2(G,H)≤7CBC2(G,H)≤7. Then, we prove that if H⊆GH⊆G is a forest whose connected components are paths, then CBC2(G,H)≤6CBC2(G,H)≤6.
Document type :
Journal articles
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-01246205
Contributor : Frederic Havet <>
Submitted on : Sunday, October 23, 2016 - 3:38:26 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM

File

backbone-steinberg-dam.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01246205, version 1

Collections

Citation

Julio Araujo, Frédéric Havet, Mathieu Schmitt. Steinberg-like theorems for backbone colouring. Electronic Notes in Discrete Mathematics, Elsevier, 2015, LAGOS'15 – VIII Latin-American Algorithms, Graphs and Optimization Symposium, 50, pp.223-229. ⟨hal-01246205⟩

Share

Metrics

Record views

738

Files downloads

217