What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Questions tagged [graph-colouring]

The tag has no usage guidance.

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
428 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 ...
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 ...
87 views

### How much is known about coloring of planar graphs with degree bounds?

Are there any references that address the following (open?) questions: 1) Is there an algorithm that 4-colors any planar graph of maximal degree at most 5 in linear time? 2) What is the largest ...
122 views

### General Results for Complicated Constraint Satisfaction Problem

Consider the following problem: on a finite two-dimensional grid (say the grid points are vertices of a graph), I need to color the vertices in such a way to satisfy the existence and nonexistence of ...
95 views

110 views

### Path-width and chromatic number

How would I prove that the chromatic number of a graph $G$ is smaller than or equal to the path-width of $G$ + 1? or $\chi(G) \leq pw(G) + 1$
Let $G$ be a complete graph edge-colored with $k$ colors. We say that $G$ is Gallai-colored if no triangle is colored with three distinct colors. Fix a tuple of integers $c = (c_1,\ldots,c_k)$. We may ...