1 Search Results for "Dyrseth, Jakob"

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.43
On the Complexity of Rainbow Vertex Colouring Diametral Path Graphs

Authors: Jakob Dyrseth and Paloma T. Lima

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Given a graph and a colouring of its vertices, a rainbow vertex path is a path between two vertices such that all the internal nodes of the path are coloured distinctly. A graph is rainbow vertex-connected if between every pair of vertices in the graph there exists a rainbow vertex path. We study the problem of deciding whether a given graph can be coloured using k or less colours such that it is rainbow vertex-connected. Note that every graph G needs at least diam(G)-1 colours to be rainbow vertex connected. Heggernes et al. [MFCS, 2018] conjectured that if G is a graph in which every induced subgraph has a dominating diametral path, then G can always be rainbow vertex coloured with diam(G)-1 many colours. In this work, we confirm their conjecture for chordal, bipartite and claw-free diametral path graphs. We complement these results by showing the conjecture does not hold if the condition on every induced subgraph is dropped. In fact we show that, in this case, even though diam(G) many colours are always enough, it is NP-complete to determine whether a graph with a dominating diametral path of length three can be rainbow vertex coloured with two colours.
Cite as

Jakob Dyrseth and Paloma T. Lima. On the Complexity of Rainbow Vertex Colouring Diametral Path Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dyrseth_et_al:LIPIcs.ISAAC.2022.43,
  author =	{Dyrseth, Jakob and Lima, Paloma T.},
  title =	{{On the Complexity of Rainbow Vertex Colouring Diametral Path Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.43},
  URN =		{urn:nbn:de:0030-drops-173286},
  doi =		{10.4230/LIPIcs.ISAAC.2022.43},
  annote =	{Keywords: rainbow vertex colouring, diametral path graphs, interval graphs}
}
  • Refine by Author
  • 1 Dyrseth, Jakob
  • 1 Lima, Paloma T.

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 diametral path graphs
  • 1 interval graphs
  • 1 rainbow vertex colouring

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact