(I understand this must be a late answer; i am writing for future readers) There is an evern stronger result in the literature. Cubic Planar Positive 1-in-3 Satisfiability is proved NP-complete in ...

Surprise! (for me). This type of matchings are already studied in the literature. They are called connected matchings. They were introduced by Plummer, Stiebitz and Toft in their study on Hadwiger ...

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

It is not a gap-preserving reduction, but an approximation factor preserving reduction. The comment by Manuel Lafond is very close to an answer (but I cannot concur with the opinion that having same ...

It is studied in the literature. It is the coloring variant called fall coloring introduced by Dunbar et al . Quote from  (I have made minute changes in the language): A coloring of a graph $G=(... View answer 2 votes This result is included in Ore's book The Four-Colour Problem (see Theorem 7.4.3). I saw a paper that states this as a folklore result and cites Ore. Interestingly, the book gives a different proof ... View answer Accepted answer 2 votes Yes, the counting version of 1-in-3 Sat is$\#P$-complete. This is stated in "Complexity of Generalized Satisfiability Counting Problems" (Example 3.1), the reference pointed out by Emil in the ... View answer Accepted answer 1 votes Conjecture 1: Every 4-colourful Eulerian orientation of 𝐺 is a good Eulerian orientation. This is the conjecture made in the question. We now have a counter-example to Conjecture 1. That is, we have ... View answer Accepted answer 1 votes 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)... View answer Accepted answer 1 votes Conjecture 2 is already proved. Quote from J.A. Tilley, The a-graph coloring problem(2017): Theorem A.1. Let$G$be an a-graph with boundary cycle$uxvy$for the exterior 4-face and let$G$have a 4-... View answer 1 votes For all$k\geq 3$, the problem maximum induced matching is APX-hard for$k$-regular bipartite graphs. See this paper. A matching$M$of a graph$G$is induced if for every pair of edges$e,e'$in M, ... View answer 1 votes There is another way to put this question. Is there a perfect matching$M$of a balanced bipartite graph$G$such that every pair of edges in$M$is exactly at a distance 1 from each other in$G\$ ? ( ...