Jernej
Reputation
2,260
Top tag
Next privilege 2,500 Rep.
Create tag synonyms
 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))$ Jan 18 awarded Popular Question Jan 16 comment Applications of Prüfer sequence If you count theoretical applications as well then it allows one to prove that the complete graph on $n$ vertices has $n^{n-2}$ spanning trees (Cayley theorem) Jan 7 awarded Nice Question Dec 12 awarded Yearling Dec 9 comment Are there any vertex colouring algorithms which colour regular graphs optimally? Not in general but if this is meant to be practical then a integer program may work well if your graphs are not too large Dec 6 revised A triangle-free, 6-chromatic graph with 44 vertices added 1 character in body Dec 5 comment Eigenvalues of graphs The trace of $A_G$ corresponds to the sum of its eigenvalues. Since $\rm{tr}{A_G} = 0$ it follows that any graph with at least one edge must have a negative eigenvalue Dec 5 revised A triangle-free, 6-chromatic graph with 44 vertices added 135 characters in body Dec 5 revised A triangle-free, 6-chromatic graph with 44 vertices added 135 characters in body Dec 5 answered A triangle-free, 6-chromatic graph with 44 vertices Dec 2 comment how to construct non-Hamiltonian graphs Simply make them disconnected. Take for example The six cycle $C_6$ with degree sequence $(2,2,2,2,2,2)$ and two disjoint 3-cycles $C_3 \cup C_3$ which has the same degree sequence. Nov 29 comment Graph Automorphisms and Induced Subgraphs A first natural question in this direction is (analogous as for the orbits) whether almost all graphs have a trivial partition under $\sim$. If this is true (which I'd say it is) then there is not much you can say in general if you're given $\sim$ Nov 26 comment Comparison of Graphs (Adjecency List/Matrix) Isomorphism software is already available in the form of libraries (nauty, bliss) and if you don't care about the interface I'd recommend using Sage. Implementing a good isomorphism tester from scratch might be overkill Nov 26 comment Comparison of Graphs (Adjecency List/Matrix) Perhaps I misunderstand but to me it seems that you need to test these molecules for isomorphism? Is this question of a theoretical nature or do you need to do this in practice? Nov 25 revised Graph Isomorphism for non-mathematician added 54 characters in body