# Tag Info

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