caa a22 4500 467909768 CHVBK 20180406152846.0 cr unu---uuuuu 170328e20060301xx s 000 0 eng 10.1007/s00037-005-0201-2 doi (NATIONALLICENCE)springer-10.1007/s00037-005-0201-2 Marx Dániel Department of Computer Science and Information Theory, Budapest University of Technology and Economics, H-1521, Budapest, Hungary aut The complexity of chromatic strength and chromatic edge strength [Elektronische Daten] [Dániel Marx] Abstract.: The sum of a coloring is the sum of the colors assigned to the vertices (assuming that the colors are positive integers). The sum ∑ (G) of graph G is the smallest sum that can be achieved by a proper vertex coloring of G. The chromatic strength s(G) of G is the minimum number of colors that is required by a coloring with sum ∑ (G). For every k, we determine the complexity of the question "Is s(G) ≤ k?”: it is coNP-complete for k = 2 and Θ2p-complete for every fixed k ≥ 3. We also study the complexity of the edge coloring version of the problem, with analogous definitions for the edge sum ∑′(G) and the chromatic edge strength s′(G). We show that for every k ≥ 3, it is Θ2p-complete to decide whether s′(G) ≤ k. As a first step of the proof, we present graphs for every r ≥ 3 with chromatic index r and edge strength r + 1. For some values of r, such graphs have not been known before. Birkhäuser Verlag, Basel, 2005 Graph coloring nationallicence chromatic strength nationallicence chromatic number nationallicence chromatic index nationallicence 68Q17 nationallicence computational complexity Birkhäuser-Verlag; www.birkhauser.ch 14/4(2006-03-01), 308-340 1016-3328 14:4<308 2006 14 37 https://doi.org/10.1007/s00037-005-0201-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-005-0201-2 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Marx Dániel Department of Computer Science and Information Theory, Budapest University of Technology and Economics, H-1521, Budapest, Hungary aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhauser.ch 14/4(2006-03-01), 308-340 1016-3328 14:4<308 2006 14 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer