# Questions tagged [graph-colouring]

The tag has no usage guidance.

80 questions
Filter by
Sorted by
Tagged with
21 views

### Complexity of K-Colorful Coloring Problem for a Hypergraph

I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem ...
57 views

### Determine if a graph has exactly 1 cycle using a SAT solver

I have a connected undirected graph whose edges are either enabled or disabled. I want to create a set of clauses that are SAT iff all enabled edges are part of a single loop. If I assert that each ...
79 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 ...
28 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 ...
156 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?
72 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 ...
28 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?
74 views

226 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 ...
102 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$
71 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: ...
536 views

### Hard problems for bounded vertex cover

We know that list coloring problem is W-hard when parameterized by vertex cover. Are there any other problems which are also W-hard parameterized by vertex cover?
143 views

574 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?
504 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 ...
71 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 ...
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 ...
73 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 ...
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$. ...
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-...
685 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. ...
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$ ...
279 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 ...
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 ...
417 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 ...
347 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 ...
123 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 ...
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 ...
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 ...
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 ...
480 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 ...
308 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 ...
587 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.
931 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-...
141 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 ...
283 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 ...
444 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 ...
8k 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?
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 ...