# Questions tagged [graph-colouring]

The tag has no usage guidance.

127 questions
Filter by
Sorted by
Tagged with
102 views

### Complexity of 2-coloring with extra constraints

I am considering the following problem: Given a graph $G=(V,E)$ with $|V|=4n$ vertices, can we color the vertices in two colors (red and blue) with The usual constraint that two vertices connected by ...
• 121
62 views

### why is there the need for a reduction between clique and multicoloured clique?

I do not understand why we need to make a reduction from k-clique to k-multicoloured clique. Any k-clique can only be coloured in k different colours since each pair of vertices is adjacent. So it ...
54 views

### Hardness of deciding fractional chromatic number at most $k$

I want to find a reference for the following statement. Here, $\chi_f(G)$ denotes the fractional chromatic number of a graph $G$. For every fixed $r>2$, deciding $\chi_f(G) \leq r$ for a given ...
42 views

### Hardness of Coloring based on a Black-Box Hardness of Independent Set

It is well known that both vertex coloring and maximum independent set are very hard to approximate in polynomial time under standard complexity assumptions. Given a black-box hardness of independent ...
• 412
1 vote
123 views

154 views

### Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?

Planar graphs are 4-colorable. Determining if a planar graph is 3-colorable is NP-Complete. A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable. ...
92 views

### How many more colours do you need if you add to $G$ a maximum matching from $G^c$?

The title says it all. Let $G$ be a (simple undirected finite) graph, and let $G^c$ be the complement of $G$ (i.e. contains edges not in $G$ and no more). Let $M$ be a perfect matching in $G^c$. How ...
• 1,817
364 views

### Coloring where all colors are present in closed neighborhood of every vertex

I am interested in (proper) vertex colorings of graphs with the following condition: for every vertex $v$ in the graph, all colors should be present in the closed neighborhood of $v$. Is this studied ...
• 1,817
129 views

### A conjecture on 4-coloring maximal planar graphs

The question/task is to prove/disprove the conjecture below. Let $G$ be a maximal planar graph with a 4-coloring $f$. Let $(a,b,c,d)$ be a cycle in $G$. Let $S$ be the collection of all $a,c$-paths in ...
• 1,817
169 views

• 1,817
300 views

### Is there a planar 4-regular graph that is 3-acyclic colourable?

A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours). Burstein proved that 4-regular graphs are 5-acyclic colourable. It seems to me ...
• 1,817
102 views

### Producing colouring of maximal planar graphs G from colouring of dual of G

A (simple) graph is said to be maximal planar if it is planar and adding one more edge loses planarity. In other words, the graph is planar and every face is a triangle. Tait gave a one-one ...
• 1,817
142 views

### On the coloring number of small graphs with small cliques

Given a parameter $k$, and a graph $G$ with $O(k^2)$ vertices that has a maximum clique with $\le k$ vertices, I want to investigate the maximum number of colors $C(k)$ needed to properly color $G$, i....
• 475
1 vote
52 views

### K-Uniform Hypergraph Strong Coloring [closed]

I want to ask if strong coloring of a k-uniform hypergraph using only k colors is NP-Hard or NP-Complete? If you can add a reference this will be helpful.
• 11
115 views

### Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

This question is on "Vertex Partitioning Problems" framework of Telle and Proskurowski. For solving problems in parital $k$-trees (i.e., graphs of bounded treewidth), the "Vertex ...
• 1,817
278 views

### Complexity of graph isomorphism with properly colored edges (ref. request)

An edge-colored graph $G$ is a graph whose edges are labeled with a color (generally represented by an integer). Such a coloring is proper if all adjacent edges in $G$ have different colors. I ...
2k views

### Computing the edge orbits of a graph (and discussing definitions)

A (vertex) automorphism in a graph $G=(V,E)$ is a permutation $\sigma$ of the vertices that preserves adjacency, namely $\sigma(u) \sigma(v) \in E$ if and only if $uv \in E$. The automorphisms of a ...
136 views

• 7
879 views

### 3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
• 625
1 vote
67 views

### Directed Acyclic Graph partition into minimum subgraphs with a constraint

I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
• 111
95 views

### Which computational framework lies behind the Chinese “Social Credit System”?

BACKGROUND The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
• 149