Questions tagged [graph-colouring]
The graph-colouring tag has no usage guidance.
1
vote
1answer
68 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
25 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
69 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
116 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
99 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 $\...
-1
votes
1answer
214 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
97 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$
2
votes
0answers
69 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
513 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
137 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
187 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
93 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 ...
8
votes
1answer
218 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 ...
0
votes
0answers
59 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
382 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)=...
-5
votes
1answer
437 views
What is the complexity of the fastest method of k-coloring any graph? [closed]
I heard brute-force is the only method. Is there any other way? Is there a way to prove that the complexity cannot be exponential?
5
votes
1answer
456 views
Canonical way of coloring graphs (individualization) for isomorphism purpose
Stefan Kratsch and Pascal Schweitzer in their paper
Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs
give a characterization of graphs on which
Graph Isomorphism ...
0
votes
1answer
69 views
Number of rounds of iterative one-round distributed color reduction
We are talking about one-round coloring algorithms for distributed graphs.
In "On the complexity of distributed graph coloring" (theorem 5.1) Kuhn and Wattenhoffer presented a one-round algorithm to ...
6
votes
1answer
290 views
NP-hardness of coloring uniform hypergraphs
Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable for $k=1,2$ is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen ...
7
votes
0answers
72 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 ...
5
votes
1answer
108 views
Existence of certain graph gadget related to coloring odd hole free graph
Crossposted from MO.
Wondering about the existence of graph gadget related to coloring
(or 3-coloring) odd hole free graphs.
Let $G$ be simple $k$-chromatic connected graph with two
vertices $u,v$.
...
1
vote
1answer
179 views
Two paper appear to imply collapse via coloring $P_5$-free graphs
Found this from graphclasses.org.
Two papers give conflicting results for coloring $P_5$-free
graphs which appear to imply $P=NP$.
From Polynomial-time algorithm for vertex k-colorability of P_5-...
12
votes
1answer
674 views
Have these coloring games been solved?
In the paper "On the complexity of some coloring games", Bodlaender gives some open questions about the complexity of deciding if player 1 or 2 has a winning strategy in some graph coloring games. ...
1
vote
0answers
29 views
Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart
Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...
3
votes
2answers
276 views
Graphs whose maximal clique intersection graph has bounded chromatic number
In general,
The chromatic number of the clique intersection graph a graph can again be arbitrarily high.
For example, take $n$ maximal cliques of size $n$ such that every pair of maximal cliques has ...
6
votes
0answers
121 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 ...
16
votes
0answers
413 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 ...
7
votes
1answer
341 views
The Overfull conjecture in graph theory and $coNP$
I am not good at complexity, but got a possible
relation between a plausible conjecture in graph
theory and $coNP$.
Graph $G$ is Class 1 if it can be edge colored
with $\Delta(G)$ colors, otherwise ...
2
votes
1answer
121 views
For which graph classes the fractional chromatic index rounded up equals the chromatic index?
Let $\chi'_f(G)$ be the fractional chromatic index.
For which graph classes $\lceil \chi'_f(G) \rceil = \chi'(G)$?
Since $\chi'_f(G)$ is computable in polynomial time,
solving this gives tractable ...
0
votes
0answers
133 views
An interesting class of colored graphs?
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 ...
1
vote
0answers
120 views
Chromatic number of a graph where neighbourhood of each vertex is isomorphic
Consider a graph $G(V,E)$. For any two vertices $v_1 , v_2 \in V$, the subgraph induced by the neigbourhood of vertex $v_1$, denoted by $G_{v_1}$ be isomorphic to the subgraph induced by the ...
6
votes
2answers
724 views
Anti-chromatic number
What is the maximum number of colors that can be used for coloring the vertices of a given graph, with no isolated vertices, such that each vertex should share its color with at least one of its ...
5
votes
1answer
473 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 ...
7
votes
1answer
297 views
Chromatic number of G+v where G is a cograph
Cograph is a well-know graph that does not have induced $P_4$. My questions are about determining the chromatic number of graphs in the class cograph+v.
Notations:
Denote by $\chi(G)$ the chromatic ...
11
votes
3answers
583 views
Graph coloring minimizing the number of colors in every independent set
Is the following claim known?
Claim: For any graph $G$ with $n$ vertices there exists a coloring of $G$ such that every independent set is colored by at most $O(\sqrt{n})$ colors.
8
votes
1answer
892 views
How bad can the greedy coloring (list color) for the c-chromatic number of graph be?
c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a P4-...
2
votes
1answer
139 views
Complexity of Haemers' minimum rank
In 1978 Willem H. Haemmers published "An upper bound on the Shannon capacity of a graph".
Tims has a survey of more recent results his thesis.
What is the computational complexity of computing ...
5
votes
1answer
262 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 ...
10
votes
2answers
443 views
Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs
I heard of a result in approximate graph coloring, but cannot find the source. The result is:
For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph ...
2
votes
1answer
7k views
Flood fill vs depth first search
Is the flood fill algorithm the same as depth first search?
If not, how do they differ in complexity?
6
votes
2answers
341 views
Decision problem related to coloring
Given a $k$-colorable graph $G$ and vertices $u$ and $v$ of $G$, what is the complexity of deciding if every $k$-coloring of $G$ must assign the same color to both $u$ and $v$?
It does not seem ...
17
votes
1answer
891 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 ...
12
votes
2answers
1k views
Small graph with gap between chromatic and vector chromatic number?
I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$.
($G$ has vector chromatic number $q$ if there is an assignment $x\colon V ...
12
votes
4answers
1k 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 ...
21
votes
5answers
2k 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 ...
15
votes
1answer
598 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 ...
3
votes
1answer
168 views
bounded outdegree bipartite spanners
Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties :
$G'$ ...
4
votes
1answer
628 views
Path coloring in general graphs
Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors.
We know that coloring a set of paths ...
11
votes
1answer
220 views
An improper planar coloring with monochromatic component size $\leq 2$
Let us relax the coloring a little bit, that is, we allow a small number of adjacent vertices to be assigned the same color. A monochromatic component is defined to be a connected component in the ...
26
votes
1answer
851 views
Coloring complexity of graphs
Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ ...
