# Tagged Questions

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

32 views

### Label coloring to maximize number of “balanced” triangles (NP-hardness)

Define a triangle in undirected graph $G$ is balanced if the edge labels in the triangle are $(+1, +1, +1)$, $(-1, -1, +1)$, $(+1, -1, -1)$ or $(-1, +1, -1)$ (social balance theory). Problem ...
68 views

### How to color sudoku with this added constraint?

I couldn't figure out an algorithm for following graph coloring problem: Output color of each vertex for this graph: Given a solved 9*9 sudoku board that is a 9-colored board, applied first three ...
28 views

### Euler graph k-coloring (np-completeness proof)

I've been studying np-completeness proofs by reduction, and was wondering whether my approach to the following problem is viable. Define an Euler graph as a graph that 1) is connected, and 2) has ...
319 views

### Showing that 3-colorable is NP-complete

Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color? I'...
356 views

### How to prove that 3-coloring is decidable?

In order to prove that 3-coloring is decidable, is it sufficient to say: Each node in the graph has 3 possible colors Therefore we can enumerate over all $3^n$ possibilities and then check that no ...
51 views

### Minimal number of animals in a matching card game [closed]

I saw a card game designed for small children. Each card has a picture of 6 animals on it, and there are 31 cards. When any two cards are compared to each other, they share exactly one animal. The ...
31 views

### Edge Covering with different colored edges

I have a graph with the edges already assigned colors and there are edges of the same color as well as different colors incident to each vertex. I would like to find an edge cover (does not have to ...
108 views

### Graph Families that are easy to color

What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter. Examples would be: Kneser graphs Chordal graphs Do ...
191 views

### Counter example to graph coloring heuristic using BFS

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 ...
47 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 ...
40 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 ...
93 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 ...