TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Computing minimum rainbow and strong rainbow colorings of block graphs

Tutkimustuotosvertaisarvioitu

Standard

Computing minimum rainbow and strong rainbow colorings of block graphs. / Keranen, Melissa; Lauri, Juho.

julkaisussa: Discrete Mathematics and Theoretical Computer Science, Vuosikerta 20, Nro 1, 22, 2018.

Tutkimustuotosvertaisarvioitu

Harvard

Keranen, M & Lauri, J 2018, 'Computing minimum rainbow and strong rainbow colorings of block graphs', Discrete Mathematics and Theoretical Computer Science, Vuosikerta. 20, Nro 1, 22. https://doi.org/10.23638/DMTCS-20-1-22

APA

Keranen, M., & Lauri, J. (2018). Computing minimum rainbow and strong rainbow colorings of block graphs. Discrete Mathematics and Theoretical Computer Science, 20(1), [22]. https://doi.org/10.23638/DMTCS-20-1-22

Vancouver

Keranen M, Lauri J. Computing minimum rainbow and strong rainbow colorings of block graphs. Discrete Mathematics and Theoretical Computer Science. 2018;20(1). 22. https://doi.org/10.23638/DMTCS-20-1-22

Author

Keranen, Melissa ; Lauri, Juho. / Computing minimum rainbow and strong rainbow colorings of block graphs. Julkaisussa: Discrete Mathematics and Theoretical Computer Science. 2018 ; Vuosikerta 20, Nro 1.

Bibtex - Lataa

@article{cab7dcfabf08457482e6d378f68d3cb9,
title = "Computing minimum rainbow and strong rainbow colorings of block graphs",
abstract = "A path in an edge-colored graph G is rainbow if no two edges of it are colored the same. The graph G is rainbowconnected if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph G is strongly rainbow-connected. The minimum number of colors needed to make G rainbow-connected is known as the rainbow connection number of G, and is denoted by rc(G). Similarly, the minimum number of colors needed to make G strongly rainbow-connected is known as the strong rainbow connection number ofG, and is denoted by src(G). We prove that for every k ≥ 3, deciding whether src(G) ≤ k is NP-complete for split graphs, which form a subclass of chordal graphs. Furthermore, there exists no polynomial-time algorithm for approximating the strong rainbow connection number of an n-vertex split graph with a factor of n1-2-ϵ for any ϵ > 0 unless P = NP. We then turn our attention to block graphs, which also form a subclass of chordal graphs. We determine the strong rainbow connection number of block graphs, and show it can be computed in linear time. Finally, we provide a polynomial-time characterization of bridgeless block graphs with rainbow connection number at most 4.",
keywords = "Block graph, Computational complexity, Rainbow coloring",
author = "Melissa Keranen and Juho Lauri",
year = "2018",
doi = "10.23638/DMTCS-20-1-22",
language = "English",
volume = "20",
journal = "Discrete Mathematics and Theoretical Computer Science",
issn = "1462-7264",
number = "1",

}

RIS (suitable for import to EndNote) - Lataa

TY - JOUR

T1 - Computing minimum rainbow and strong rainbow colorings of block graphs

AU - Keranen, Melissa

AU - Lauri, Juho

PY - 2018

Y1 - 2018

N2 - A path in an edge-colored graph G is rainbow if no two edges of it are colored the same. The graph G is rainbowconnected if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph G is strongly rainbow-connected. The minimum number of colors needed to make G rainbow-connected is known as the rainbow connection number of G, and is denoted by rc(G). Similarly, the minimum number of colors needed to make G strongly rainbow-connected is known as the strong rainbow connection number ofG, and is denoted by src(G). We prove that for every k ≥ 3, deciding whether src(G) ≤ k is NP-complete for split graphs, which form a subclass of chordal graphs. Furthermore, there exists no polynomial-time algorithm for approximating the strong rainbow connection number of an n-vertex split graph with a factor of n1-2-ϵ for any ϵ > 0 unless P = NP. We then turn our attention to block graphs, which also form a subclass of chordal graphs. We determine the strong rainbow connection number of block graphs, and show it can be computed in linear time. Finally, we provide a polynomial-time characterization of bridgeless block graphs with rainbow connection number at most 4.

AB - A path in an edge-colored graph G is rainbow if no two edges of it are colored the same. The graph G is rainbowconnected if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph G is strongly rainbow-connected. The minimum number of colors needed to make G rainbow-connected is known as the rainbow connection number of G, and is denoted by rc(G). Similarly, the minimum number of colors needed to make G strongly rainbow-connected is known as the strong rainbow connection number ofG, and is denoted by src(G). We prove that for every k ≥ 3, deciding whether src(G) ≤ k is NP-complete for split graphs, which form a subclass of chordal graphs. Furthermore, there exists no polynomial-time algorithm for approximating the strong rainbow connection number of an n-vertex split graph with a factor of n1-2-ϵ for any ϵ > 0 unless P = NP. We then turn our attention to block graphs, which also form a subclass of chordal graphs. We determine the strong rainbow connection number of block graphs, and show it can be computed in linear time. Finally, we provide a polynomial-time characterization of bridgeless block graphs with rainbow connection number at most 4.

KW - Block graph

KW - Computational complexity

KW - Rainbow coloring

U2 - 10.23638/DMTCS-20-1-22

DO - 10.23638/DMTCS-20-1-22

M3 - Article

VL - 20

JO - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

SN - 1462-7264

IS - 1

M1 - 22

ER -