# 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 ...

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 ...

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 $... 0 The result mentioned in the question can be obtained by a chain of two standard reductions. The simplest reduction for$k$-COLORABILITY$\leq_p(k+1)$-COLORABILITY (namely, adding a universal vertex) is clearly a linear reduction. Also, the reduction$k$-COLORABILITY$\leq_pk$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil\$) given by Emden-Weinert ...

Top 50 recent answers are included