# Questions tagged [graph-colouring]

The tag has no usage guidance.

99 questions
Filter by
Sorted by
Tagged with
944 views

3k views

### Reasons for which a graph may be not $k$ colorable?

While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to ...
1k views

### Coloring Planar Graphs

Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can ...
487 views

### Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the ...
940 views

### What is the complexity of this edge coloring problem?

Recently, I have encountered the following variant of edge coloring. Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying ...
634 views

### Why are perfect graphs called perfect?

Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is ...
433 views

### Is graph coloring complete for poly-APX?

Is the graph coloring problem complete for poly-APX under C-reductions (alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
2k views

### Complexity of edge coloring in planar graphs

3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". What is the complexity of 3-edge coloring of cubic ...
413 views

### Question on Products of Graphs

Let $S_{n}(G)$, $C_{n}(G)$, $T_{n}(G)$ be the $n$-fold Strong Product, Cartesian Product and Tensor Product of a graph $G$ on $|V|$ vertices. Let the chromatic number ($\chi(G)$) and the independence ...
2k views

### hardness of approximating the chromatic number in graphs with bounded degree

I am looking for hardness results on vertex coloring of graphs with bounded degree. Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
1k views

382 views

### Worst case ratio between minimum clique cover and maximum independent set

The maximum independent set problem gives a lower bound for the minimum clique cover problem. This is easy to see because given any clique cover together with an independent set, any two vertices ...
541 views

### Chromatic number of planar graph with girth at least k

The four-color theorem claims that, any loopless planar graph is 4-colorable. However, it is NP-Complete to determine the chromatic number of planar graphs, even for those 4-regular ones. Girth is ...
Assume I have a parametrized graph. The parameters are two integers $x$ and $y<x$. Let $S(x)=\{1, \ldots, x\}$. The vertices of the graph are all the subsets of $S(x)$ of size $y$. Two vertices ...