Questions tagged [graph-colouring]
The graph-colouring tag has no usage guidance.
110
questions
1
vote
1answer
35 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
votes
0answers
37 views
How does Cycle Decomposition become Colored-Edges?
If it is said that, for a generator $σ \in S$ (the set of generator of a group), edges can be added to a directed edge-colored graph $X(G)$ of color $σ$ corresponding to the cycle decomposition of $σ$,...
2
votes
1answer
140 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.
2
votes
1answer
149 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
vote
0answers
100 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 ...
1
vote
0answers
88 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 ...
4
votes
1answer
205 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
vote
1answer
54 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 ...
3
votes
1answer
280 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 (...
3
votes
2answers
86 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
vote
2answers
98 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 |(...
9
votes
0answers
130 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
1answer
80 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 ...
3
votes
2answers
142 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 ...
2
votes
1answer
83 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 ...
2
votes
0answers
162 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 $\...
3
votes
0answers
78 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 ...
3
votes
0answers
139 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 ...
4
votes
2answers
296 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 ...
2
votes
1answer
119 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) $...
10
votes
1answer
204 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 ...
2
votes
1answer
78 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
vote
0answers
70 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)$) ...
2
votes
2answers
121 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....
1
vote
0answers
47 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.
2
votes
2answers
110 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 ...
8
votes
1answer
206 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 ...
7
votes
2answers
521 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 ...
-4
votes
1answer
123 views
10
votes
1answer
406 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 ...
1
vote
0answers
54 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 ...
2
votes
0answers
84 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 ...
2
votes
0answers
39 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
vote
0answers
172 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?
3
votes
0answers
279 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-...
1
vote
1answer
103 views
Color shifting in a bipartite graph
Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the ...
2
votes
0answers
31 views
Heuristics for exact #3COLORING close to the 3-colorability threshold
What are some fast heuristics for exactly counting 3-colorings of graphs close to or at the 3-colorability threshold? Is there literature on the average-case performance for any of these methods?
4
votes
0answers
104 views
2-hop distributed coloring in the CONGEST model
Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$.
A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
3
votes
0answers
152 views
Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$? [closed]
We got an argument that 3-coloring bounded degree graphs is subexponential
with complexity $O(\exp{(\sqrt{n}\log^2{n})})$.
The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$
and 3-...
1
vote
1answer
133 views
How good of an approximate 2-coloring can you get of the halved cube graph?
We say that a 2-coloring $col : V_G \rightarrow \{0, 1\}$ of a graph $G$ is $\epsilon$-approximate if $Pr_{(w, v) \in E_G}(col(w) \neq col(v)) \geq \epsilon$. For every $n$, what is the maximum $\...
0
votes
1answer
275 views
3-coloring graph zero-knowledge proof [closed]
I was researching about zero-knowledge proofs and in this link http://web.mit.edu/~ezyang/Public/graph/svg.html I've seen the exercise question:
Currently, you can only select adjacent pairs of nodes ...
0
votes
0answers
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$
1
vote
0answers
73 views
Describe the condition of “non-adjacent 3-cycles” in terms of the cubic adjacency matrix
Oleg Borodin and André Raspaud
"A sufficient condition for planar graphs to be 3-colorable"
Journal of Combinatorial Theory B88, 2003, 17–27
state the following conjecture:
Conjecture 1.2:
...
7
votes
3answers
638 views
Hard problems for bounded vertex cover
We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?
1
vote
1answer
159 views
Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known
Given a $k>0$ and a graph $G(V,E)$ with known independence number $\sqrt{|V|}\leq\alpha(G)\leq\alpha\sqrt{|V|}$ and chromatic number $\frac1\beta\sqrt{|V|}\leq\chi(G)\leq\sqrt{|V|}$ for some fixed $...
9
votes
1answer
226 views
What is known about the hardness of the chromatic index for restricted graph classes?
There is a nice paper from 1991 that contains three diagrams about different graphclass-families showing what is known about the hardness of determining the chromatic index for them.
Are there any ...
3
votes
1answer
122 views
What is the recognition complexity of k-uniform k-partite hypergraphs? [duplicate]
We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied.
It's also ...
7
votes
1answer
251 views
3-color a cubic graph such that a MIS receives only two colors
According to Brooks'_theorem, a cubic graph (3-regular graph) containing no $K_4$ can be properly colored by three colors. (Such a color can actually be found in linear time, which is not our primary ...
1
vote
0answers
67 views
About complexity of recovering or learning Bayesian networks
Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
2
votes
1answer
544 views
Partition into triangles in a 3-partite graphe
Let $G=(X\cup Y\cup Z,E)$ be a 3-partite graph such that:
$|X|=|Y|=|Z|=q$.
$2 \leq d(v) \leq 6$ for all $v \in X\cup Y\cup Z$, where $d(v)$ is the degree of v.
$\sum_{x \in X} d(x)=\sum_{y \in Y}d(y)=...
