Cyriac Antony
  • Member for 4 years, 1 month
  • Last seen this week
  • India
3 answers
11 votes
2k views
2 bookmarks
"Almost all objects have property P" vs. "It is easy to test whether an object has property P"
2 answers
11 votes
347 views
1 bookmarks
Maximum matching M with the condition G[M] is 2K_2-free
1 answers
10 votes
235 views
Is there a planar 4-regular graph that is 3-acyclic colourable?
1 answers
5 votes
97 views
1 bookmarks
Upperbound for max degree of k-tree completion
2 answers
4 votes
223 views
Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?
1 answers
4 votes
219 views
1 bookmarks
Complexity of relaxed edge colouring
2 answers
4 votes
376 views
3-colourability of Eulerian maximal planar graph
1 answers
3 votes
292 views
ETH based lower bound for $k$-COLORING of bounded degree graph
2 answers
3 votes
97 views
Graph labelling where vertices with a common neighbour get different labels
0 answers
3 votes
79 views
Computing chromatic number of subcubic graphs
2 answers
3 votes
145 views
Coloring where all colors are present in closed neighborhood of every vertex
0 answers
3 votes
141 views
Uniquely 4-colorable Planar Graph Conjecture?
1 answers
2 votes
69 views
On cubic planar graphs with face boundaries of length divisible by 4
1 answers
2 votes
54 views
1 bookmarks
Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?
1 answers
2 votes
197 views
Does abundance of max cliques make it easy to solve COLORABILITY?
0 answers
2 votes
55 views
Complexity of a matrix partition problem in graphs
1 answers
2 votes
160 views
1 bookmarks
Is the difference between the acyclic chromatic number and the star chromatic number unbounded?
2 answers
2 votes
362 views
Proving not NP-complete by non-existence of gadget
0 answers
2 votes
102 views
1 bookmarks
Size of the constant $s_3$ in Exponential Time Hypothesis (ETH)
0 answers
2 votes
49 views
Internal as well as external partition of (regular) graphs
2 answers
2 votes
112 views
Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?
1 answers
2 votes
95 views
A conjecture on 4-coloring maximal planar graphs
1 answers
2 votes
146 views
Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices
1 answers
2 votes
125 views
Who proved that a triangulation is 3-colourable implies its dual is bipartite
1 answers
2 votes
82 views
Producing colouring of maximal planar graphs G from colouring of dual of G
0 answers
2 votes
169 views
Book recommendation treewidth
0 answers
1 votes
35 views
Does high connectivity of line graph of $G$ imply high (cyclic) connectivity of $G$?
0 answers
1 votes
39 views
Cycle double covers of cubic graphs using only a few cycles
0 answers
1 votes
26 views
Cycle decompositions of locally linear 4-regular graphs
0 answers
1 votes
41 views
Properties of half-way locally bijective homomorphisms between Eulerian orientations