Rainbow Colouring of Split and Threshold Graphs

DOI10.1007/978-3-642-32241-9_16MaRDI QIDQ2914323zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, Deepak Rajendraprasad

Publication date 25 September 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.1670, http://eprints.iisc.ac.in/47703/1/1205.1670.pdf

zbMATH Keywords

complexityapproximationchordal graphsdegree sequencerainbow connectivitysplit graphsrainbow colouringthreshold graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Abstract: A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k larger than 2, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.

Recommendations

• Rainbow colouring of split graphs
• On colorings of split graphs
• Rainbow matchings in edge-colored complete split graphs
• Vertex rainbow colorings of graphs
• On rainbow total-coloring of a graph
• Rainbow graph splitting
• Rainbow mean colorings of graphs
• Rainbow dominator coloring in graphs
• Rainbow structures in locally bounded colorings of graphs
• Rainbow saturation of graphs

Cited in

(11)

• A survey on rainbow (vertex-)index of graphs
• Algorithms and bounds for very strong rainbow coloring
• Rainbow connection number and graph operations
• Rainbow tetrahedra in Cayley graphs
• Rainbow vertex coloring bipartite graphs and chordal graphs
• Rainbow graph splitting
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• Rainbow colouring of split graphs
• On the fine-grained complexity of rainbow coloring
• Rainbow connectivity and rainbow criticality on graph classes
• Fine-grained complexity of rainbow coloring and its variants

This page was built for publication: Rainbow Colouring of Split and Threshold Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2914323)