dc.creator | Castro Ochoa, Natalia de | es |
dc.creator | Garrido Vizuete, María de los Angeles | es |
dc.creator | Robles Arias, Rafael | es |
dc.creator | Villar Liñán, María Trinidad | es |
dc.date.accessioned | 2021-09-14T09:28:00Z | |
dc.date.available | 2021-09-14T09:28:00Z | |
dc.date.issued | 2020 | |
dc.identifier.citation | Castro Ochoa, N.d., Garrido Vizuete, M.d.l.A., Robles Arias, R. y Villar Liñán, M.T. (2020). Contrast in Greyscales of Graphs. Journal of Combinatorial Optimization, 39 (3), 874-898. | |
dc.identifier.issn | 1382-6905 | es |
dc.identifier.uri | https://hdl.handle.net/11441/125724 | |
dc.description.abstract | In this paper,we present the notion of greyscale of a graph, as a colouring of its vertices
that uses colours from the continuous spectrum [0, 1]. Any greyscale induces another
colouring by assigning to each edge the non-negative difference between the colours
of its vertices. These edge colours are ordered in lexicographical increasing order and
make up the contrast vector of the greyscale. The aim of the contrast problem for the
given graph is to find the maximum contrast vector and the greyscales that give rise
to it, namely the maximum contrast greyscales. The NP-completeness of this problem
is stated by means of a functional relation between the chromatic number and the
first component of the maximum contrast vector, named the lightest tone. Thus, we
introduce the notion of lightest tone as a new invariant of the graph. The underlying
structure of values of maximum contrast greyscales is addressed and we prove that
they are linked by rational number sets, which are algorithmically determined. The
restricted maximum contrast problem, that is, greyscales with prefixed extreme tones,
is also defined and solved in polynomial time for different families of bipartite graphs. | es |
dc.description.sponsorship | Ministerio de Economía, Industria y Competitividad MTM2015-65397-P | es |
dc.description.sponsorship | Junta de Andalucía PAI FQM-164 | es |
dc.format | application/pdf | es |
dc.format.extent | 25 | es |
dc.language.iso | eng | es |
dc.publisher | Springer | es |
dc.relation.ispartof | Journal of Combinatorial Optimization, 39 (3), 874-898. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Graph colouring | es |
dc.subject | Greyscale | es |
dc.subject | Maximum contrast | es |
dc.subject | NP-completeness | es |
dc.title | Contrast in Greyscales of Graphs | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Geometría y Topología | es |
dc.relation.projectID | MTM2015-65397-P | es |
dc.relation.projectID | PAI FQM-164 | es |
dc.relation.publisherversion | https://link.springer.com/article/https://link.springer.com/article/10.1007/s10878-020-00528-w | es |
dc.identifier.doi | 10.1007/s10878-020-00528-w | es |
dc.journaltitle | Journal of Combinatorial Optimization | es |
dc.publication.volumen | 39 | es |
dc.publication.issue | 3 | es |
dc.publication.initialPage | 874 | es |
dc.publication.endPage | 898 | es |
dc.contributor.funder | Ministerio de Economia, Industria y Competitividad (MINECO). España | es |
dc.contributor.funder | Junta de Andalucía | es |