Contrast in greyscales of graphs

DOI10.1007/S10878-020-00528-WMaRDI QIDQ2307508zbMATH OpenOpenAlexFDO

Authors Natalia de Castro, María A. Garrido-Vizuete, R. Robles, María Trinidad Villar Liñán

Publication date 24 March 2020

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.07527

zbMATH Keywords

graph colouringgreyscalemaximum contrastNP-completeness

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Minimax problems in mathematical programming (90C47)

Abstract: A greyscale $f$ of a graph $G(V,E)$ is a mapping from $V$ to the interval $[0,1]$ such that $0,1subseteqIm(f)$. This function $f$ induces another mapping $widehatf$ on $E$ by assigning to each edge the non-negative difference of the values of $f$ on its vertices. The contrast vector $cont(G,f)$ is defined as the vector $(widehatf(e_1),widehatf(e_2),ldots,widehatf(e_m))$ for all edges $e_i$ of $G$ in such a way that $widehatf(e_i)leqwidehatf(e_{i+1})$ for $i=1,2,dots,m-1$. The concept of maximum contrast vector is presented by using the lexicographical ordering in the set of contrast vectors of all possible greyscales defined on $G$ and a greyscale that gives rise to a maximum contrast vector is named maximum contrast greyscale. The relation between finding the maximum contrast vector for the graph $G$ and the chromatic number of $G$ is established. Thus the maximum contrast problem is an NP-complete problem. However, the set of values of any maximum contrast greyscale for any graph is bounded by a finite set which is given. Several methods to compute the maximum contrast vector with some restrictions in are collected in this paper.

Recommendations

• Minimum gradation in greyscales of graphs
• Gray code numbers for graphs
• On maximum differential graph coloring
• A contrast maximization method for color-to-grayscale conversion
• Further Results on T-Coloring and Frequency Assignment Problems

Cites work

• An exact algorithm for the edge coloring by total labeling problem
• Bounds on spectrum graph coloring
• Choosing Colors for Geometric Graphs Via Color Space Embeddings
• Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks
• Graph labellings with variable weights, a survey
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimum gradation in greyscales of graphs
• Minimum sum coloring problem: upper bounds for the chromatic strength
• Models and solution techniques for frequency assignment problems
• On maximum differential graph coloring
• On some applications of the selective graph coloring problem
• On Some Variants of the Bandwidth Minimization Problem
• Parallel concepts in graph theory
• Reducibility among combinatorial problems
• Spectrum graph coloring and applications to Wi-Fi channel assignment
• Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction
• The maximum \(k\)-differential coloring problem

Cited in

(2)

• Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction
• Minimum gradation in greyscales of graphs

Describes a project that uses

Uses Software

• CALMA

This page was built for publication: Contrast in greyscales of graphs

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