# Questions tagged [graph-colouring]

The tag has no usage guidance.

104 questions
Filter by
Sorted by
Tagged with
1answer
183 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 ...
1answer
51 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 ...
1answer
248 views

### ETH based lower bound for $k$-COLORING

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 (...
2answers
82 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}$ ...
2answers
86 views

0answers
77 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 ...
0answers
138 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 ...
2answers
185 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 ...
1answer
115 views

0answers
147 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-...
1answer
124 views

1answer
225 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 ...
1answer
116 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 ...
1answer
247 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 ...
0answers
65 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 ...
1answer
535 views