Cyriac Antony
  • Member for 4 years, 1 month
  • Last seen this week
  • India
Limited number of variable occurrences in 1-in-3 SAT
6 votes

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

View answer
Maximum matching M with the condition G[M] is 2K_2-free
Accepted answer
5 votes

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

View answer
Graph labelling where vertices with a common neighbour get different labels
Accepted answer
3 votes

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

View answer
Hardness of approximating acyclic chromatic number
Accepted answer
3 votes

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

View answer
Coloring where all colors are present in closed neighborhood of every vertex
Accepted answer
2 votes

It is studied in the literature. It is the coloring variant called fall coloring introduced by Dunbar et al [1]. Quote from [1] (I have made minute changes in the language): A coloring of a graph $G=(...

View answer
Who proved that a triangulation is 3-colourable implies its dual is bipartite
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
Is the counting version of 1-in-3 Sat #P-complete?
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
Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?
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
ETH based lower bound for $k$-COLORING of bounded degree graph
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
A conjecture on 4-coloring maximal planar graphs
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
Problems that are NP-hard to approximate even when the input graph is regular
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
Maximum matching M with the condition G[M] is 2K_2-free
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$ ? ( ...

View answer
Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?
Accepted answer
0 votes

Thanks to M. kanté for pointing out further papers that studied this framework. Reading later papers that deal with vertex partioning problem framework (mostly under the name LS-VSP problems) resolved ...

View answer