User Cyriac Antony

6 votes

Limited number of variable occurrences in 1-in-3 SAT

answered Mar 30, 2019 at 6:15

5 votes

Accepted

Maximum matching M with the condition G[M] is 2K_2-free

answered Nov 29, 2019 at 16:46

3 votes

Accepted

Hardness of approximating acyclic chromatic number

answered Feb 25, 2020 at 10:09

3 votes

Accepted

Graph labelling where vertices with a common neighbour get different labels

answered Apr 2, 2021 at 9:26

3 votes

Structural Complexity Theory References

answered Aug 24, 2023 at 9:36

2 votes

Exact algorithm for NAE-3SAT

answered Mar 28, 2022 at 9:11

2 votes

Who proved that a triangulation is 3-colourable implies its dual is bipartite

answered Jul 1, 2020 at 10:53

2 votes

Accepted

Coloring where all colors are present in closed neighborhood of every vertex

answered Nov 14, 2020 at 15:17

2 votes

Accepted

Is the counting version of 1-in-3 Sat #P-complete?

answered Jan 20, 2020 at 10:55

1 vote

Problems that are NP-hard to approximate even when the input graph is regular

answered Jan 29, 2020 at 7:02

1 vote

Accepted

A conjecture on 4-coloring maximal planar graphs

answered Oct 15, 2020 at 6:35

1 vote

Upper Bound for distance-two chromatic number in terms of maximum degree

answered Aug 23, 2023 at 11:25

1 vote

Accepted

Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?

answered Jan 1, 2022 at 2:23

1 vote

Maximum matching M with the condition G[M] is 2K_2-free

answered Mar 7, 2018 at 9:07

1 vote

Accepted

ETH based lower bound for $k$-COLORING of bounded degree graph

answered Mar 31, 2021 at 5:23

0 votes

Accepted

Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

answered Jan 2, 2021 at 3:59

Stack Exchange Network

16 Answers

Limited number of variable occurrences in 1-in-3 SAT

Maximum matching M with the condition G[M] is 2K_2-free

Hardness of approximating acyclic chromatic number

Graph labelling where vertices with a common neighbour get different labels

Structural Complexity Theory References

Exact algorithm for NAE-3SAT

Who proved that a triangulation is 3-colourable implies its dual is bipartite

Coloring where all colors are present in closed neighborhood of every vertex

Is the counting version of 1-in-3 Sat #P-complete?

Problems that are NP-hard to approximate even when the input graph is regular

A conjecture on 4-coloring maximal planar graphs

Upper Bound for distance-two chromatic number in terms of maximum degree

Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?

Maximum matching M with the condition G[M] is 2K_2-free

ETH based lower bound for $k$-COLORING of bounded degree graph

Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?