Skip to main content

Questions tagged [colorings]

Questions on graph coloring, an assignment of colors to elements of a graph subject to specific constraints.

Filter by
Sorted by
Tagged with
1 vote
1 answer
41 views

Reducing the Independent Set Problem to Independent Set for 3-Colorable Graphs

I am exploring a reduction from the general Independent Set Problem to the Independent Set Problem specifically for 3-colorable graphs. The goal is to demonstrate that the maximal independent set of a ...
Ferran Gonzalez's user avatar
0 votes
1 answer
46 views

Algorithm for 3-coloring a graph, given a search algorithm that finds a k-colored graph for $k \ge 4$ if one exists, and otherwise returns false

The problem statement is: Given a search algorithm that finds and returns a k-colored graph for $k \ge 4$ if one exists, and otherwise returns false, show that there exists a search algorithm for 3-...
Yoxbox's user avatar
  • 5
3 votes
2 answers
677 views

Is 2-coloring in NL or L?

The 2-coloring problem is in P. How can I prove that it is in NL or L? I see that I should create a deterministic/nondeterministic algorithm with logarithmic space, but I have no idea how to store ...
knorbika's user avatar
2 votes
1 answer
77 views

Proof that the K coloring problem is weakly or strong NP-complete?

As far as I know, the K coloring problem is NP-complete. However, I'm a bit confused about how to determine whether a problem is weakly or strongly NP-complete. If an NP-complete problem is decidable ...
wellknow's user avatar
1 vote
2 answers
116 views

NP-hardness of modified distance-colouring of graphs

Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
r236's user avatar
  • 11
3 votes
0 answers
30 views

Why is there no self-stabilizing determinsitic algorithm for vertex coloring in general graphs?

This question considers the design of a deterministic self-stabilizing algorithm for vertex coloring in uniform anonymous networks. Uniform anonymous networks do not have distinguished nodes and all ...
NoName123's user avatar
  • 171
0 votes
1 answer
46 views

Let 3-COL-$K_4$-FREE be the decision problem that asks if a graph that doesn't contain $K_4$ admits a 3-coloring. Show that the problem is NP-complete

I'm kind of struggling with this excercise. The obvious thing to try is to show that 3-COL $\leq_p$ 3-COL-$K_4$-FREE ($\leq_p$ stands for polynomial reduction). It is clear that 3-COL-$K_4$-FREE is in ...
nicoyanovsky's user avatar
1 vote
0 answers
27 views

Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds

Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system: 1: Assume that initially the nodes have IDs of size $\log(n)$ bits 2: The root is ...
Gabi G's user avatar
  • 325
0 votes
0 answers
29 views

How to calculate transition areas of biomes in an image

I'm generating biomes for my game and I would like to store them in a single RGB image like the one below. A color hue can then be mapped to an ID through a table lookup. The problem I face is that I ...
nights's user avatar
  • 101
1 vote
1 answer
55 views

How to generate all possible colour vectors generated by greedy colouring on a graph?

Given a graph $G$, how can we generate all possible color vectors that could be generated via greedy coloring? N.B. Greedy coloring takes a graph and an order of vertices. It traverses vertices ...
Subhankar Ghosal's user avatar
0 votes
0 answers
25 views

Best function to preserve information after decreasing color depth?

Let's assume, I have a grayscale image that every pixel represented with 8 bits. I want to quantize (decrease color depth) the image into 2 bits. Hence, I need a function as $f:A\rightarrow B$ where $...
unique's user avatar
  • 101
0 votes
0 answers
34 views

Separate recipes into compatible categories

We are running a restaurant. Unfortunately due to mysterious reasons, we cannot tell our chef what recipes to make, we can only prepare him the ingredients for the meals. Fortunately our chef has ...
Igor Vereš's user avatar
0 votes
0 answers
212 views

Solving graph coloring problem using genetic algorithms

I have some basic information about the graph coloring problem, which is an NP-Complete problem. I am very new to genetic algorithms, and I have faced a problem in which we have to solve the graph ...
Aylin Naebzadeh's user avatar
0 votes
2 answers
46 views

What are the definitions of countable and measurable colourings of a graph?

In this paper, the author discusses colourings of the plane, or in other words, of the underlying graph. I suppose a finite colouring is a colouring using at most $k$ colours for some natural number $...
J. Schmidt's user avatar
1 vote
1 answer
534 views

What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?

First Few Iterations of the Algorithm We have an algorithm in which a squirrel visits the nodes of a directed graph. Our graph has two colors of edges: black and white. Initially, the graph has black ...
Toothpick Anemone's user avatar
2 votes
2 answers
613 views

Graph Injective-Homomorphism Problem

Graph Homomorphism is a well-known NP-complete problem. Given graph $G$ and $H$, $G$ is said to be homomorphic to $H$ if there is a mapping $f: V(G) \mapsto V(H)$ such that $(u,v) \in E(G) \implies (f(...
Brian's user avatar
  • 129
3 votes
1 answer
97 views

Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?

Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$? A ...
Subhankar Ghosal's user avatar
1 vote
0 answers
238 views

With fixed k>=4, can 3-coloring in a graph of vertex degree at most k be solved in polynomial time?

I couldn't think of a poly-time solution. Moreover, I think that there is a pretty simple Karp-reduction from 3-coloring problem, which is NP-complete. let's say that graph G is in 3-colloring. I'll ...
AllForCode's user avatar
1 vote
1 answer
430 views

How to find the lightest path that has at least one vertex of each color?

I've faced this question in my homework. In a graph $G=(V,\ E)$ where every $v\in V$ has a color, a colored path is a path such that it has at least one vertex of each color. We're given a directed ...
Mohamad S.'s user avatar
0 votes
0 answers
57 views

Understanding edge coloring for graphs

I'm working on a graph problem that basically boils down to an edge-coloring problem. I have a graph where all vertices have (at most) an in-degree of 2 and an out-degree of 1. I thought this would ...
jaip's user avatar
  • 25
1 vote
1 answer
118 views

Fastest way to find optimal graph coloring in polynomial space given chromatic number

Suppose I have a graph's chromatic number. Give a faster-than-brute-force polynomial-space algorithm for finding an optimal coloring. If such an algorithm isn't known, please tell me so. This question ...
user2373145's user avatar
1 vote
1 answer
25 views

Current state of polynomial-space exact graph coloring

The fastest algorithm I could find that finds the chromatic number of an undirected simple graph exactly in only polynomial-space is "Faster Graph Coloring in Polynomial Space" by Gaspers ...
user2373145's user avatar
2 votes
0 answers
48 views

On the complexity of equitable $k$-coloring split graphs

The Wikipedia article on Equitable coloring states that A polynomial time algorithm is known for equitable coloring of split graphs. The referred paper also seems to achive the proposed polynomial ...
NoteMyQuestion's user avatar
2 votes
1 answer
163 views

Meaning of "approximation within $n^{1−\epsilon}$"

I am not sure I understand correctly the following assertion (source): For all $\epsilon > 0$, approximating the chromatic number within $n^{1−\epsilon}$ is NP-hard. Does this mean that, for any ...
Aristide's user avatar
  • 323
3 votes
0 answers
90 views

Graph coloring problem with violations

I would like a name for the following problem. We consider a relaxed vertex coloring problem, where Let $k$ be the number of colors Let $B$ be the set of edges violating coloring, i.e., $$B := \{(u,...
Dmitry's user avatar
  • 345
3 votes
1 answer
30 views

On a coloring that uses $2\cdot a\left( G \right)$ colors

Denote $G=\left( V, E \right)$ arboricity by $a\left( G \right)$. I'm trying to understand why $G$ is $2\cdot a \left( G \right)$-colorable. I came across this post. Both the OP and the answer say ...
Dan D-man's user avatar
  • 524
3 votes
0 answers
87 views

Coloring nodes and edges in node-weighted graph

I have a graph $G$ with $n$ nodes and $O(n)$ edges. Each of the nodes has a positive integral weight at least 2, such that sum of all weights is at most $O(n)$. We want to color the nodes and edges ...
Rajarshi basu's user avatar
2 votes
1 answer
37 views

On the relation between several graph parameters

Recently, I came across several parameters of graphs. So I know in general graphs, it might be hard to compare between them, but I'd like to try and see which upper/lower bounds can be made. Some ...
Dan D-man's user avatar
  • 524
4 votes
1 answer
152 views

Attempting to verify the colorability using Wigderson's Algorithm

The algorithm of Wigderson (see here) can color a graph that is known to be $3$-colorable in $O\left( \sqrt{\left| V \right|} \right)$ colors. This is done in $O\left( |V| + |E|\right)$ time. For ...
TheEmeritus's user avatar
2 votes
1 answer
543 views

Currently best approximation for graph coloring

As we all know it is $NPH$ to check whether $G=(V,E)$ is $k$-colorable or not. It is also hard to find the chromatic number of $G$. But I'd like to ask what are some good (or best known) approximation ...
Mařík Savenko's user avatar
0 votes
1 answer
83 views

Boolean formula for graph 3COL

For a given undirected graph $G=(V,E)$ I'm trying to construct a boolean polynomially computable formula $\varphi$ with the following property: $\varphi$ is satisfiable $\iff$ vertices of $G$ can be ...
Andy's user avatar
  • 115
3 votes
1 answer
66 views

Using the chromatic number to compute an optimal coloring

Suppose we are given a graph $G$ of order $n$ and a black box that can efficiently (polynomial time) compute the chromatic number $\chi(G)$. I am curious to hear how would one go about in order to ...
Jernej's user avatar
  • 2,460
8 votes
1 answer
449 views

Optimality of DSATUR on interval graphs

The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of (number of different ...
Nathaniel's user avatar
  • 15.8k
3 votes
1 answer
62 views

Equally coloring the edges of square tiles that form a grid

I need to generate a set of square tiles that are colored and are grid-able. Each square tile must have a unique set of 4 colors and each exterior edge of each tile is colored with a different color. ...
Rosco Schock's user avatar
1 vote
1 answer
219 views

How many colors will be used in the following bipartite graph

I decided to create an algorithm to find the colors that is used to color a bipartite graph, the algorithm proceeds as follows: Rename the vertices in a some order $v_1,v_2,\ldots,v_n$. Do a single ...
Toothless's user avatar
4 votes
1 answer
118 views

What is a guarenteed amount of colors, depending on the graph's arboricity

Let $G=(V,E)$ and denote $d=d(G)$ its maximal degree and $a=a(G)$ its arboricity. My question is: what is the smallest amount of colors $f(a)$, such that a $f(a)$-coloring is guarenteed to exist? For ...
Eric_'s user avatar
  • 445
0 votes
1 answer
475 views

Color coding to get an FPT algoirthm for k disjoint triangles

The k-disjoint triangles problem is as follows: Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$ Output: Are there $k$ vertex-disjoint triangles in $G$? An FPT algorithm is presented here (...
KSGG's user avatar
  • 11
1 vote
1 answer
148 views

Time complexity for FPT algorithm

I'm studying the issue of FPT algorithms and came to the k-disjoint triangles problem as can be seen here on slide 60. The problem summary is given a graph G and variable k, are there k disjoint ...
jsitesting's user avatar
1 vote
1 answer
175 views

k disjoint triangles with graph splitting to two distinct groups

Please note that this question is different than this question. The $k$-disjoint triangles problem is as follows: Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$ Output: Are there $k$ ...
JoshHalas's user avatar
  • 203
1 vote
1 answer
126 views

Polynomial kernelization for Set Splitting

In a set system $(U, F)$, $F\subseteq \mathcal{P}(U))$, we say that a function $f: U \to \{0, 1\}$ is a coloring of $(U, F)$. A set in $F$ is split by $f$ if $F$ receives both colors. The Set ...
Michal Dvořák's user avatar
1 vote
1 answer
89 views

Triangles covering all vertices of a tri-partite graph

This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers. I'm designing fictional fruits. Each fruit has three attributes; color, taste ...
Rohit Pandey's user avatar
2 votes
1 answer
121 views

Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time

I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. ...
user2373145's user avatar
2 votes
1 answer
70 views

How to avoid monochromatic cycles?

I am working on the following exercise: Consider a simple and connected undirected graph $G(V,E)$. Show that one can colour the edges of $G$ in polynomial time and with as few colours as possible ...
3nondatur's user avatar
  • 457
1 vote
0 answers
39 views

Would a five color display have higher image quality than an RGB display?

We have five types of photo receptors in the eyes but computer color systems just use the three red, green and blue. Three could be motivated if rod and melanopsin sensations are just linear ...
David Jonsson's user avatar
1 vote
1 answer
210 views

What does it mean that a set of intervals is sorted by the right and left endpoints?

While reading a paper (On the k-coloring of intervals), I came upon the following description: "Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are ...
Sebastian Allard's user avatar
0 votes
3 answers
262 views

What makes an algorithm greedy?

I have a simple graph $G = (V,E)$ and each vertex has a range $[a,b]$. Every two vertices are connected only if $[a_1, b_1]$ and $[a_2, b_2]$ have a common subrange. Each range of vertex is rV1 = [0,5]...
Demokles's user avatar
1 vote
1 answer
409 views

NPC-problem reduction to triangle-free 3-colorability

lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find ...
kolomann's user avatar
1 vote
1 answer
700 views

If each pixel contains the channels for the 3 primary colours, why can a 1-bit picture only be presented in white and black?

I'm an igsce student. I'm taking computer science as an OL subject this year. Pixels are the small squares which make an image. Inside each pixel there are 3 channels: one for blue, one for green, one ...
Manar's user avatar
  • 133
1 vote
1 answer
193 views

Another version of the 3-coloring decision problem?

Given a graph $G$, is there a 3-coloring with colors $c1$, $c2$ and $c3$ such that at most $k$ nodes are given the color $c1$ and that no two adjacent nodes are given the same color? Is there a ...
user avatar
2 votes
1 answer
255 views

shortest path in color-weighted graphs

I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum ...
Andre's user avatar
  • 21