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

learn more… | top users | synonyms

0
votes
0answers
18 views

Counter example to graph coloring heuristic using BFS [on hold]

I am considering the following heuristic for the graph coloring problem (i.e. to color a graph $G$ using a minimal number of colors so that no two adjacent vertices have the same color): Explore ...
1
vote
0answers
16 views

Coloring a 3-Colorable graph with O(logn) colors

Assume we have a polynomial algorithm that can get approximation ratio of $\frac{1}{2}$ to the Independent-Set problem. I need to prove that there exists a polynomial algorithm that for a 3-Colorable ...
1
vote
1answer
25 views

How do you produce a CNF from a circular graph with colouring?

If you had a circular graph e.g. A->B->C->D->E->A, and a legal coloring system with 3 colours (e.g. Red, Green Blue), where each node is assigned a colour and no node can be connected to another node ...
1
vote
2answers
61 views

Complexity of 4-coloring a map with constraints

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color. In fact, there exists a ...
2
votes
0answers
86 views

Marking nodes of a complete binary tree

Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of ...
0
votes
1answer
44 views

All but Five Three Colorable

An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 ...
5
votes
1answer
75 views

Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to ...
0
votes
0answers
18 views

Assign colors to vertices of a 3 colorable graph [duplicate]

Black Box tell is g(v,e) is 3 colorable or not. How can we use this graph to assign the colors to a 3 colorable graph?
1
vote
1answer
52 views

3-Coloring Problem Question [duplicate]

So I understand that finding a solution to the 3-coloring problem takes exponential time. However, say you had a friend who you could give a graph G to and he can say in constant time whether it is ...
0
votes
2answers
51 views

Does 2-edge-colourability imply 2-colourability?

Why is it that if the edges of an undirected graph G can be grouped into two sets such that every vertex is incident to at most 1 edge from each set, then the graph is 2-colorable. The reason that I ...
1
vote
1answer
20 views

Why do Benes networks form bipartite graphs when you build a constraint graph for them?

I was learning about Benes networks and was wondering why they formed bipartite graphs (and thus are two colorable) when one draws a constraint graph for them. The constraint graph is based on the ...
8
votes
1answer
95 views

What is the name of the problem? (partitioning graph into three covers)

I was wondering if this problem has a name: Given a simple graph whose edges are colored red, blue and green, $G=(V,B\cup R\cup G)$, is there a vertex-coloring $c:V\to \{B,R,G\}$ such that every edge ...
-2
votes
1answer
39 views

How to figure out the minimal number of colors needed to color specific given graphs?

I found this question on the net and I'm wondering what is the process for answering such questions? I assume there is some formula that works for all graphs? 1.a. Consider the undirected graph with ...
3
votes
3answers
820 views

Application of Four color theorem

I was reading up on Four color theorem and am wondering if there is any practical application of it .( I dont think seperating the map into four different colors can be considered an application) I ...
0
votes
1answer
354 views

Find largest chromatic number of a full binary tree [closed]

This is a Discrete Math/Combinatorics Question from my hw…but I don't really understand the question. Find largest chromatic number of a full binary tree given the following depths: (Check all ...
3
votes
3answers
336 views

Characterisation of graphs that are not 3-colorable

We know that all graphs with odd cycles (odd number of vertices) are not 2-colorable. Is there a similar characterisation for 3-colorability? I am looking for undirected graphs that are not ...
2
votes
1answer
121 views

Relaxed graph coloring, with penalties for assigning adjacent vertices the same color

Consider a set of $N$ nodes. There is a $N\times N$ non-negative valued matrix $D$ where the $(i,j)$th element $d_{ij}$ gives the "positive metric" between node $i$ and $j$, where $i,j\in [N]$. Thus ...
5
votes
1answer
182 views

A variation of the graph coloring problem

Given a set of colors $M$ and a graph $G=(V,E)$. Allocate the colors to minimize the number edges with same color on the two vertices of the edge (i.e. minimize pairs of adjoining vertices with same ...
1
vote
2answers
234 views

Calculate number of ways to color matrix using inclusion-exclusion principle

This was asked in a recent contest. The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same ...
2
votes
1answer
101 views

Strategic vertex labeling

We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0. The problem is to ...
1
vote
1answer
60 views

Prove that 2-Colourability is in L from Undir-Reachability is in L

Let Undir-Reachability be the following problem: given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G? I need to prove that the 2-Colourability is in ...
8
votes
2answers
287 views

6-coloring of a tree in a distributed manner

I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^*n)$ time. The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse ...
5
votes
1answer
321 views

Distributed 6-color Vertex Coloring

I am trying to understand the distributed 6-color algorithm for vertex coloring (on page 10). Here is a short description Idea of the algorithm: We start with color labels that have $\log n$ bits. ...
10
votes
2answers
845 views

Chromatic polynomial of a square

Consider a square, ABCD. Intuitively it seemed to me that its chromatic polynomial is $\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$ where there are $\lambda$ colours available.. That is there are ...
5
votes
0answers
113 views

Beating fair colorings with few edges

I have been investigating parallel algorithms to compute certain two-dimensional dynamic programming recursions (on natural parameters); see also here. Under certain assumptions, cases one and two can ...