## Hardness results for rainbow disconnection of graphs. (arXiv:1811.11939v1 [math.CO])

Let $G$ be a nontrivial connected, edge-colored graph. An edge-cut $S$ of $G$ is called a rainbow cut if no two edges in $S$ are colored with a same color. An edge-coloring of $G$ is a rainbow disconnection coloring if for every two distinct vertices $s$ and $t$ of $G$, there exists a rainbow cut $S$ in $G$ such that $s$ and $t$ belong to different components of $G\setminus S$. For a connected graph $G$, the {\it rainbow disconnection number} of $G$, denoted by $rd(G)$, is defined as the smallest number of colors such that $G$ has a rainbow disconnection coloring by using this number of colors. In this paper, we show that for a connected graph $G$, computing $rd(G)$ is NP-hard. In particular, it is already NP-complete to decide if $rd(G)=3$ for a connected cubic graph. Moreover, we prove that for a given edge-colored (with an unbounded number of colors) connected graph $G$ it is NP-complete to decide whether $G$ is rainbow disconnected. 查看全文>>

﻿
{"ft_lang_label":"__label__en","ft_lang_prob":0.84712243,"math_prob":0.9998956,"size":1068,"snap":"2020-34-2020-40","text_gpt3_token_len":308,"char_repetition_ratio":0.15507519,"word_repetition_ratio":0.0,"special_character_ratio":0.26498127,"punctuation_ratio":0.098130845,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99989986,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-08-11T04:23:30Z\",\"WARC-Record-ID\":\"<urn:uuid:dc0611cc-f84f-459d-a29e-aa72c4538ae8>\",\"Content-Length\":\"14362\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:5f08bdda-e76e-4cb4-ad13-4d5a4b82e17f>\",\"WARC-Concurrent-To\":\"<urn:uuid:1b92bc52-379e-40e7-a731-e4598b26f321>\",\"WARC-IP-Address\":\"106.75.14.181\",\"WARC-Target-URI\":\"https://www.solidot.org/news/view?id=145275\",\"WARC-Payload-Digest\":\"sha1:TQMOITZ5BUMEWPO4LQLI7OOVGTS2WKUG\",\"WARC-Block-Digest\":\"sha1:MEIEHN5YWDXEV7UG37AY27BUJ4WQPWVJ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-34/CC-MAIN-2020-34_segments_1596439738727.76_warc_CC-MAIN-20200811025355-20200811055355-00378.warc.gz\"}"}