User Cyriac Antony

13 votes

3 answers

2k views

"Almost all objects have property P" vs. "It is easy to test whether an object has property P"

asked Jan 20, 2020 at 6:20

11 votes

2 answers

364 views

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

asked Mar 6, 2018 at 5:00

10 votes

1 answer

337 views

Is there a planar 4-regular graph that is 3-acyclic colourable?

asked Jun 9, 2020 at 6:43

6 votes

0 answers

391 views

Is Gnang's proof of Graceful Tree Conjecture correct?

asked Jun 22 at 6:00

5 votes

2 answers

856 views

3-colourability of Eulerian maximal planar graph

asked Jun 22, 2020 at 9:38

5 votes

1 answer

125 views

Upperbound for max degree of k-tree completion

asked Oct 8, 2020 at 4:59

4 votes

2 answers

273 views

Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?

asked Dec 16, 2020 at 6:19

4 votes

1 answer

239 views

Complexity of relaxed edge colouring

asked Apr 13, 2021 at 7:13

4 votes

0 answers

172 views

Uniquely 4-colorable Planar Graph Conjecture?

asked Jul 12, 2020 at 6:17

4 votes

0 answers

233 views

Book recommendation treewidth

asked Jul 24, 2019 at 6:02

3 votes

1 answer

242 views

Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices

asked Sep 7, 2020 at 12:10

3 votes

0 answers

94 views

Computing chromatic number of subcubic graphs

asked Sep 16, 2020 at 16:03

3 votes

2 answers

132 views

Graph labelling where vertices with a common neighbour get different labels

asked Mar 20, 2021 at 5:53

3 votes

1 answer

372 views

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

asked Mar 25, 2021 at 7:30

3 votes

2 answers

378 views

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

asked Nov 13, 2020 at 7:03

3 votes

1 answer

175 views

On cubic planar graphs with face boundaries of length divisible by 4

asked Jan 11, 2022 at 4:32

3 votes

0 answers

48 views

Does high connectivity of line graph of $G$ imply high (cyclic) connectivity of $G$?

asked Jan 17, 2022 at 7:59

3 votes

1 answer

96 views

Name for set of vertices that are pairwise within distance two

asked Mar 7, 2022 at 11:01

2 votes

1 answer

79 views

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

asked Mar 29, 2022 at 6:16

2 votes

0 answers

69 views

Is k-ACYCLIC COLOURABLITY in CSP?

asked May 4, 2022 at 5:16

2 votes

1 answer

208 views

Does abundance of max cliques make it easy to solve COLORABILITY?

asked Nov 8, 2021 at 7:05

2 votes

1 answer

82 views

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

asked Nov 9, 2021 at 11:09

2 votes

0 answers

58 views

Complexity of a matrix partition problem in graphs

asked Nov 15, 2021 at 5:35

2 votes

0 answers

65 views

Partial linear spaces and partial projective planes

asked Aug 9, 2022 at 6:39

2 votes

1 answer

131 views

A conjecture on 4-coloring maximal planar graphs

asked Oct 14, 2020 at 9:22

2 votes

0 answers

70 views

Internal as well as external partition of (regular) graphs

asked Jan 15, 2021 at 4:12

2 votes

0 answers

105 views

Size of the constant $s_3$ in Exponential Time Hypothesis (ETH)

asked Mar 18, 2021 at 7:57

2 votes

2 answers

411 views

Proving not NP-complete by non-existence of gadget

asked Apr 28, 2021 at 8:13

2 votes

1 answer

218 views

Is the difference between the acyclic chromatic number and the star chromatic number unbounded?

asked Jun 11, 2021 at 6:18

2 votes

1 answer

105 views

Producing colouring of maximal planar graphs G from colouring of dual of G

asked Jun 3, 2020 at 2:44

Stack Exchange Network

58 Questions

"Almost all objects have property P" vs. "It is easy to test whether an object has property P"

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

Is there a planar 4-regular graph that is 3-acyclic colourable?

Is Gnang's proof of Graceful Tree Conjecture correct?

3-colourability of Eulerian maximal planar graph

Upperbound for max degree of k-tree completion

Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?

Complexity of relaxed edge colouring

Uniquely 4-colorable Planar Graph Conjecture?

Book recommendation treewidth

Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices

Computing chromatic number of subcubic graphs

Graph labelling where vertices with a common neighbour get different labels

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

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

On cubic planar graphs with face boundaries of length divisible by 4

Does high connectivity of line graph of $G$ imply high (cyclic) connectivity of $G$?

Name for set of vertices that are pairwise within distance two

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

Is k-ACYCLIC COLOURABLITY in CSP?

Does abundance of max cliques make it easy to solve COLORABILITY?

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

Complexity of a matrix partition problem in graphs

Partial linear spaces and partial projective planes

A conjecture on 4-coloring maximal planar graphs

Internal as well as external partition of (regular) graphs

Size of the constant $s_3$ in Exponential Time Hypothesis (ETH)

Proving not NP-complete by non-existence of gadget

Is the difference between the acyclic chromatic number and the star chromatic number unbounded?

Producing colouring of maximal planar graphs G from colouring of dual of G