NDA@SZTAKI

F-WORM colorings: Results for 2-connected graphs

BujtĂĄs, Csilla

Tuza, Zsolt

Elsevier

2017

QA166-QA166.245 Graphs theory / grĂĄfelmĂŠlet

Given two graphs F and G, an F-WORM coloring of G is an assignment of colors to its vertices in such a way that no F-subgraph of G is monochromatic or rainbow. If G has at least one such coloring, then it is called F-WORM colorable and W−(G,F) denotes the minimum possible number of colors. Here, we consider F-WORM colorings with a fixed 2-connected graph F and prove the following three main results: (1) For every natural number k, there exists a graph G which is F-WORM colorable and W−(G,F)=k; (2) It is NP-complete to decide whether a graph is F-WORM colorable; (3) For each k≥|V(F)|−1, it is NP-complete to decide whether a graph G satisfies W−(G,F)≤k. This remains valid on the class of F-WORM colorable graphs of bounded maximum degree. We also prove that for each n≥3, there exists a graph G and integers r and s such that s≥r+2, G has Kn-WORM colorings with exactly r and also with s colors, but it admits no Kn-WORM colorings with exactly r+1,…,s−1 colors. Moreover, the difference s−r can be arbitrarily large. © 2017 Elsevier B.V.

angol

Article

PeerReviewed

info:eu-repo/semantics/article

text

http://real.mtak.hu/74269/1/1512.00478v1.pdf

BujtĂĄs, Csilla and Tuza, Zsolt (2017) F-WORM colorings: Results for 2-connected graphs. DISCRETE APPLIED MATHEMATICS, 231. pp. 131-138. ISSN 0166-218X

http://real.mtak.hu/74269/

https://doi.org/10.1016/j.dam.2017.05.008

MTMT:3279881; doi:10.1016/j.dam.2017.05.008