Jernej
Reputation
2,416
Top tag
Next privilege 2,500 Rep.
Create tag synonyms
 2d answered Is it possible to exist non-isomorphic (k,l) Ramsey graph? Apr 17 comment Is there a formula for the number of proper k-colorings of a graph $G$ up to isomorphism? @JossevanDobbendeBruyn One has to compute $\rm{Aut}(G)$. Hence, it seems to me, that this argument related to complexity invalid? In addition, the presented formula for all colorings is rather simple but it may contain exponentially many terms as well. Apr 10 comment Is the Wikipedia article about chordal graphs incorrect? $K_3$ is in fact chordal. Every cycle of length greater than 3 (none) has a chord (true) Mar 30 accepted A matrix with a dense submatrix - application of Chernoff’s Inequality Mar 25 awarded Popular Question Mar 13 answered How does the number of trees with even order that contain a perfect matching behave asymptotically? Mar 12 revised Dihedral Groups… added 3 characters in body Mar 3 comment Does the leading eigenvalue of a connected undirected graph always increase with an edge addition? @M.Badaoui If a graph $G$ has two connected components $H_1$ and $H_2$ then the eigenvalues of $G$ are the eigenvalues of $H_1$ and $H_2$. Mar 2 comment Does the leading eigenvalue of a connected undirected graph always increase with an edge addition? No, not necessarily. In fact only if $k = 1$ and $G = K_2$ Feb 28 answered Does the leading eigenvalue of a connected undirected graph always increase with an edge addition? Feb 24 comment Is there a nontrivial perfect vertex transitive graph? @JohnSmith Not sure. I guess you can always take the line graph of a vertex transitive bipartite graph. Feb 24 answered Is there a nontrivial perfect vertex transitive graph? Feb 18 answered Question about chromatic polynomial of certain graphs. Feb 18 comment On the eigenvalues of bipartite graph? There are 38 cubic bipartite graphs of order 16. Feb 17 comment On the eigenvalues of bipartite graph? I am pretty sure there is no general result in this direction. Considering just connected cubic bipartite graphs of order 16 for example (38) one can see that all but two have distinct (multi)sets of eigenvalues. Feb 1 comment Third coefficient of the chromatic polynomial given that you know $a_2$ depdens on the number of triangles, your task is then to express $t$ in terms of $|V|,|E|$ and the number of independent sets of size $3$. I am not sure that's doable without also knowing the number of $2$-paths. Feb 1 comment Non trivial results in graph theory/combinatorics coming from number theory In this paper arxiv.org/abs/1011.3376 the authors use 3-term arithmetic progressions and related number theoretical results to obtain a bound on a certain edge coloring. Feb 1 comment Third coefficient of the chromatic polynomial What exactly are you looking for ? A proof of the stated identity for $a_2$? Jan 28 comment Is there matrix representation of the line graph operator? I am sorry I don't understand. You don't know how to prove this identity? Jan 28 comment Is there matrix representation of the line graph operator? I don't know if that helps bu you can express the adjacency matrix for the line graph by using the incidence matrix. If $E$ is the incidence matrix of your graph $G$ then $E^T E - 2I = A(L(G))$