Reputation
2,260
Top tag
Next privilege 2,500 Rep.
Create tag synonyms
Badges
12 29
Impact
~55k people reached

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