6

If $G$ is $2k$-regular, then a relaxed edge coloring with exactly $k$ colors is the same thing as a 2-factorization, and is known to always exist by results of Petersen 1891. Otherwise, let $k=\lceil\Delta/2\rceil$ where $\Delta$ is the maximum degree of $G$. Then obviously, at least $k$ colors are needed in any relaxed coloring of $G$. But $G$ can be ...


3

`Special labelling' is not exactly $L(0,1)$-coloring, but is very close. In $L(0,1)$-coloring, neighboring vertices can get the same colour even if they have a common neighbor. Speciall labelling do not allow this. Special labelling is already studied in the literature under the name injective coloring. An injective colouring of a graph $G$ is a colouring $...


2

I don't know if this problem has another name, but it seems like it's easy to solve. We first see that a weak incidence coloring of a graph $G$ corresponds to an edge coloring of the graph $G'$ obtained by subdividing each edge of $G$ once. This, in turn, corresponds to a vertex coloring of $L(G')$, the line graph of $G'$. This line graph consists of a ...


2

This can take exponentially many steps, as Laakeri explained. You can build a system that cycles with period $p$. In particular, the update rule is $x_i = x_{i-1 \bmod p}$ for all $i$, with variables $x_0,\dots,x_{p-1}$. Let $p_1,\dots,p_k$ be the first $k$ primes. Concatenate $k$ disjoint systems, each of which cycles with period $p_i$. Then the period ...


2

To clarify something: [1] does not use sunlet6, but C6. More specifically, the construction is as follows: Take G, subdivide every edge once, then make each old vertex additionally be part of its own new 6-cycle. In other words, if G has n vertices and m edges, G' has 6n + m vertices and 6n + 2m edges. The description you give isn't quite the same as this. ...


2

This paper by Régis Barbanchon might be of interest. From the abstract: We prove that the Satisfiability (resp. planar Satisfiability) problem is parsimoniously P-time reducible to the 3-Colorability (resp. Planar 3-Colorability) problem, that means that the exact number of solutions is preserved by the reduction, provided that 3-colorings are counted ...


Only top voted, non community-wiki answers of a minimum length are eligible