Cyriac Antony's user avatar
Cyriac Antony's user avatar
Cyriac Antony's user avatar
Cyriac Antony
  • Member for 6 years, 2 months
  • Last seen more than a month ago
  • India
13 votes
3 answers
2k views

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

11 votes
2 answers
364 views

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

10 votes
1 answer
294 views

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

5 votes
1 answer
121 views

Upperbound for max degree of k-tree completion

4 votes
2 answers
264 views

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

4 votes
1 answer
237 views

Complexity of relaxed edge colouring

4 votes
2 answers
742 views

3-colourability of Eulerian maximal planar graph

4 votes
0 answers
168 views

Uniquely 4-colorable Planar Graph Conjecture?

4 votes
0 answers
227 views

Book recommendation treewidth

3 votes
0 answers
90 views

Computing chromatic number of subcubic graphs

3 votes
2 answers
131 views

Graph labelling where vertices with a common neighbour get different labels

3 votes
1 answer
348 views

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

3 votes
2 answers
301 views

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

3 votes
1 answer
175 views

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

3 votes
0 answers
48 views

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

3 votes
1 answer
94 views

Name for set of vertices that are pairwise within distance two

2 votes
1 answer
66 views

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

2 votes
0 answers
68 views

Is k-ACYCLIC COLOURABLITY in CSP?

2 votes
1 answer
207 views

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

2 votes
1 answer
79 views

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

2 votes
0 answers
58 views

Complexity of a matrix partition problem in graphs

2 votes
0 answers
65 views

Partial linear spaces and partial projective planes

2 votes
1 answer
127 views

A conjecture on 4-coloring maximal planar graphs

2 votes
0 answers
68 views

Internal as well as external partition of (regular) graphs

2 votes
0 answers
105 views

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

2 votes
2 answers
399 views

Proving not NP-complete by non-existence of gadget

2 votes
1 answer
207 views

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

2 votes
1 answer
101 views

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

2 votes
1 answer
217 views

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

2 votes
1 answer
230 views

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