Questions tagged [graph-colouring]
The graph-colouring tag has no usage guidance.
125
questions
1
vote
1
answer
101
views
Balanced set coloring
Let $\{S_1, S_2, ..., S_m\}$ be a collection of subsets of some universe $U$, where each $S_i$ has even size (so does $U$).
We want to color the elements of $U$, either red or blue, such that each $...
- 356
-1
votes
0
answers
50
views
Average case complexity of decision version of NP-hard problem
I am a bit confused regarding the average case complexity of certain graph problems that are NP-hard like graph coloring, clique, dominating set and whose decision version is NP-complete. It is ...
0
votes
0
answers
83
views
5-color graph and minor
We have a 5-color graph G without 5-clique. The question is: is there a minor H of G that is a 5-clique? Here the minor definition.
With "5-color graph G" I mean $\chi (G)=5$.
4
votes
1
answer
63
views
Complexity of maximum k-edge-colorable subgraph of a bipartite graph
Can the maximum $k$-edge-colorable subgraph of a bipartite graph be found in polynomial time? Equivalently, can the maximum $k$-colorable subgraph of the line graph of a bipartite graph be found in ...
- 7,465
3
votes
0
answers
67
views
Property testing algorithm for isomorphism to a balanced 3-sided complete graph
I am looking for testing algorithm in the dense graph model, that checks for a graph with $3n$ vertices whether it's isomorphic to a balanced 3-sided complete graph with $n$ vertices in each set. The ...
- 31
1
vote
1
answer
221
views
How do you achieve linear time complexity of greedy graph coloring?
In most resources I could find, greedy algorithm is described as follows:
for every vertex $v$, assign the minimal color not used by its neighbors.
The above could be implemented as:
...
11
votes
0
answers
161
views
Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$
Suppose we have a graph $G$ with maximum degree $\Delta$. Deciding if $G$ can be colored with $\Delta$ colors is easy: Brooks' theorem says that this is always possible, unless $G$ is a clique or an ...
- 3,416
3
votes
1
answer
152
views
Hardness of Maximum Independent Set in 3-Colorable Graphs
Let $G = (V,E)$ be an undirected graph such that there is a proper coloring of the vertices of $G$ in three colors.
Question: In such graphs, are there known results for the hardness of finding a ...
- 173
12
votes
1
answer
2k
views
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
- 8,896
1
vote
0
answers
20
views
Coloring the $k$-deletion graph “constructively”
For $n,k\ge 1$, we define the graph $D_{n,k}$ to have vertex set $\{0,1\}^n$, with distinct $x,y$ being adjacent if $LCS(x,y)\ge n-k$.
My question is: fixing $k>1$, does there exist some $C=C_k$ ...
- 603
5
votes
1
answer
221
views
Graph coloring with limit on number of times a color is used
Are there any results on coloring a graph using a limited number of each color. In other words, the decision problem would be: given a list of colors $C = (c_1, \dots, c_k)$ where each color $c_i$ is ...
- 53
2
votes
1
answer
62
views
Upper Bound for distance-two chromatic number in terms of maximum degree
Let us consider simple,finite, undirected graphs. A distance-two colouring of a graph $G$ is a function $f:V(G)\to\{1,2,\dots\}$ such that $f(u)\neq f(v)$ whenever $dist_G(u,v)\leq 2$. A distance-two ...
- 1,723
1
vote
1
answer
171
views
Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)
I'll preface this question by saying I have very little (zero!) knowledge of theoretical computer science, and this post is a genuine attempt to understand something, even if at an intuitive level, ...
2
votes
2
answers
267
views
When should one start looking at existing results in theoretical CS?
I'm currently a PhD student in theoretical computer science. I've been working on this problem daily for almost a month that has been well studied and was assigned to me by my advisor. The problem is ...
- 1,078
2
votes
1
answer
74
views
Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?
Let $G$ be a simple undirected plane 4-regular graph. Basic definitions are given at the bottom of this question.
An Eulerian orientation of $G$ is good if for each vertex $v$ of $G$, the edges around ...
- 1,723
2
votes
1
answer
207
views
Does abundance of max cliques make it easy to solve COLORABILITY?
Let $q\geq 3$. We know that $q$-COLORABILITY is an NP-complete problem.
Suppose that $G$ is a graph such that each vertex of $G$ is part of a $q$-clique (i.e. $K_q$). Since we may assume that $G$ does ...
- 1,723
1
vote
1
answer
51
views
Graph classes where giving a q-clique edge cover makes testing for q-colouring easy
A $q$-clique of a graph is a complete subgraph on $q$ vertices.
A $q$-clique edge cover of $G$ is a set of subgraphs of $G$ such that each subgraph is a $q$-clique and each edge of G is contained in ...
- 1,723
2
votes
1
answer
175
views
Coloring intersection graph of squares
It is known that the coloring intersection graph of axis-parallel rectangles is NP-Hard.
What about squares and more specific case "unit squares"?
Thanks.
- 21
2
votes
1
answer
198
views
Is the difference between the acyclic chromatic number and the star chromatic number unbounded?
Is $\chi_s(G)-\chi_a(G)$ unbounded in general graphs?
I thought $\chi_s(G)-\chi_a(G)$, the difference between the star chromatic number and the acyclic chromatic number, is unbounded for general ...
- 1,723
1
vote
0
answers
108
views
Has this notion of connectivity in edge-colored graphs been studied?
Consider a simple graph $G$ where each edge is either red or blue. I'm interested in the following notion of connectivity:
Two vertices $u$ and $v$ are said to be connected if there is a path ...
- 691
1
vote
0
answers
117
views
Complexity of counting 3-colourings of planar bounded degree graphs
The following are known:
It is #P-complete to count the number of 3-colourings of a planar graph (with respect to randomized reductions) [1].
For all $d\geq 3$, it is #P-complete to count the number ...
- 1,723
4
votes
1
answer
237
views
Complexity of relaxed edge colouring
A (proper) $k$-edge colouring of a graph $G(V,E)$ is a function $f:E\to\{1,2,\dots,k\}$ such that adjacent vertices are mapped to different colours; that is, $f(e)\neq f(e')$ if $e$ and $e'$ are ...
- 1,723
1
vote
1
answer
65
views
Weak incidence colouring
Let $G(V,E)$ be a simple undirected graph, let $k\in \mathbb{N}$, and let $I(G)=\{(v,e)\ :\ e\in E, v\in e \}$ (here, $v\in e$ means $v$ is incident on $e$). A $k$-incidence colouring of $G$ is a ...
- 1,723
3
votes
1
answer
344
views
ETH based lower bound for $k$-COLORING of bounded degree graph
It is known that there is no $2^{o(n)}$-time algorithm for 3-COLORABILITY of graphs of maximum degree four, unless ETH fails [1]. Is a there a similar result for $k$-COLORABILITY assuming only ETH (...
- 1,723
3
votes
2
answers
130
views
Graph labelling where vertices with a common neighbour get different labels
Is the following notion of graph labeling (let me call it special labeling) ever studied in the literature?
A special labelling of a (simple undirected) graph $G$ is a function $f:V(G)\to\mathbb{N}$ ...
- 1,723
1
vote
2
answers
127
views
Name of this graph partitioning problem? (related to coloring)
Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(...
- 693
9
votes
0
answers
149
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.
...
0
votes
1
answer
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,723
3
votes
2
answers
264
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,723
2
votes
1
answer
124
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,723
2
votes
0
answers
169
views
Complexity of Edge Coloring Regular Graphs With Large Degrees
There is an interesting series of papers on edge colorability / $1$-factorization of regular graphs with large degrees, which over the years have shown better and better lower bounds for the degree $\...
- 21
3
votes
0
answers
86
views
Computing chromatic number of subcubic graphs
According to graphclasses.org, the chromatic number of a subcubic graph can be computed in linear time (because the decision problem COLORABILITY can be solved in linear time). The reference given the ...
- 1,723
4
votes
0
answers
164
views
Uniquely 4-colorable Planar Graph Conjecture?
My question is on Uniquely 4-colorable Planar Graph Conjecture mentioned in
On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and Coloring of ...
- 1,723
4
votes
2
answers
685
views
3-colourability of Eulerian maximal planar graph
The following paragraph is from this answer by David Eppstein (emphasis mine).
A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single ...
- 1,723
2
votes
1
answer
207
views
Who proved that a triangulation is 3-colourable implies its dual is bipartite
Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent:
(i) $...
- 1,723
10
votes
1
answer
289
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,723
2
votes
1
answer
98
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,723
1
vote
0
answers
72
views
Hardness of vertex colouring on hypergraphs with $O(\log n)$ edges
I'm interested to know whether there has been any work done on the problem in the title. For the problem to be meaningful, we would naturally need that the hyperedges must have large ($\omega(1)$) ...
- 341
2
votes
2
answers
141
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
0
answers
49
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
2
votes
2
answers
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,723
8
votes
1
answer
257
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 ...
- 356
10
votes
2
answers
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 ...
- 356
-4
votes
1
answer
133
views
10
votes
1
answer
788
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 ...
- 603
1
vote
0
answers
64
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
2
votes
0
answers
94
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
2
votes
0
answers
45
views
"Planar graph coloring is not self-reducible" is this about all $p$-relations encoding that problem?
I have a question about the paper "Planar graph coloring is not self-reducible" by Samir Khuller and Vijay Vazirani.
The final theorem in that paper states that "Planar Graph k-coloring is not self ...
- 1,439
1
vote
0
answers
181
views
On planar $4$ regular graphs
It is $NP$-hard to decide if a $4$-regular planar graph can be $3$-colored.
Is an exact algorithm possible that under uniform distribution is in average polynomial time?
- 12.8k
3
votes
0
answers
313
views
Difficulty of graph coloring and independent set?
Given a graph on $n$ vertices it is strongly $NP$-complete to decide it is $3$-colorable while it is easy to decide it is $n$-colorable.
Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-...
- 539