# Questions tagged [graph-colouring]

The tag has no usage guidance.

116 questions
Filter by
Sorted by
Tagged with
25 views

### How to write a simulation to monte-carlo estimate the "probability that such a random coloring on $G$ is successful"

Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful"...
1 vote
26 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 fuction $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,623
1 vote
159 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, ...
258 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 ...
• 732
60 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,623
204 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,623
23 views

### Listing colourful Eulerian orientations in poly. time

An orientation $\overrightarrow{G}$ of an undirected graph $G$ is a directed graph obtained by assigning some direction on every edge of $G$. An orientation $\overrightarrow{G}$ is said to be an ...
• 1,623
1 vote
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,623
162 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
177 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,623
1 vote
105 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 ...
• 331
1 vote
101 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) . For all $d\geq 3$, it is #P-complete to count the number ...
• 1,623
231 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,623
1 vote
63 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,623
312 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 . Is a there a similar result for $k$-COLORABILITY assuming only ETH (...
• 1,623
113 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,623
1 vote
118 views

• 21
81 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,623
153 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,623
454 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,623
137 views

• 9,378
182 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,955
1 vote
156 views

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,552 0 votes 1 answer 336 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 ... • 119 0 votes 0 answers 112 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
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: ...
• 271