Maximal distance spectral radius of 4-chromatic planar graphs
We show that the kite graph uniquely maximizes the distance spectral radius among all connected -chromatic planar graphs on vertices.
Source author record
Aysel Erey
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
6works
1topics
3close collaborators
Published work
6 publications
preprint2021arXiv
On the average order of a dominating set of a forest
We show that the average order of a dominating set of a forest graph G on n vertices with no isolated vertices is at most 2n/3. Moreover, the equality is achieved if and only if every non-leaf vertex of G is a support vertex with one or two leaf neighbors. Our result answers an open question of Beaton and Brown.
Open access
preprint2016arXiv
A note on the real part of complex chromatic roots
A {\em chromatic root} is a root of the chromatic polynomial of a graph. While the real chromatic roots have been extensively studied and well understood, little is known about the {\em real parts} of chromatic roots. It is not difficult to see that the largest real chromatic root of a graph with n vertices is n−1, and indeed, it is known that the largest real chromatic root of a graph is at most the tree-width of the graph. Analogous to these facts, it was conjectured in [8] that the real parts of chromatic roots are also bounded above by both n−1 and the tree-width of the graph. In this article we show that for all k≥2 there exist infinitely many graphs G with tree-width k such that G has non-real chromatic roots z with ℜ(z)>k. We also discuss the weaker conjecture and prove it for graphs G with χ(G)≥n−3.
Open access
preprint2016arXiv
Extremal Restraints for Graph Colourings
A {\em restraint} on a (finite undirected) graph G=(V,E) is a function r on V such that r(v) is a finite subset of N; a proper vertex colouring c of G is {\em permitted} by r if c(v)∈r(v) for all vertices v of G (we think of r(v) as the set of colours {\em forbidden} at v). Given a large number of colors, for restraints r with exactly one colour forbidden at each vertex the smallest number of colorings is permitted when r is a constant function, but the problem of what restraints permit the largest number of colourings is more difficult. We determine such extremal restraints for complete graphs and trees.
Open access
preprint2016arXiv
New Bounds for Chromatic Polynomials and Chromatic Roots
If G is a k-chromatic graph of order n then it is known that the chromatic polynomial of G, π(G,x), is at most x(x−1)⋯(x−(k−1))xn−k=(x)↓kxn−k for every x∈N. We improve here this bound by showing that π(G,x)≤(x)↓k(x−1)Δ(G)−k+1xn−1−Δ(G) for every x∈N, where Δ(G) is the maximum degree of G. Secondly, we show that if G is a connected k-chromatic graph of order n where k≥4 then π(G,x) is at most (x)↓k(x−1)n−k for every real x≥n−2+((2n)−(2k)−n+k)2 (it had been previously conjectured that this inequality holds for all x≥k). Finally, we provide an upper bound on the moduli of the chromatic roots that is an improvment over known bounds for dense graphs.
Open access
preprint2016arXiv
On the real roots of σ-Polynomials
The σ-polynomial is given by σ(G,x)=∑i=χ(G)nai(G)xi, where ai(G) is the number of partitions of the vertices of G into i nonempty independent sets. These polynomials are closely related to chromatic polynomials, as the chromatic polynomial of G is given by ∑i=χ(G)nai(G)x(x−1)⋯(x−(i−1)). It is known that the closure of the real roots of chromatic polynomials is precisely {0, 1}⋃[32/27,∞), with (−∞,0), (0,1) and (1,32/27) being maximal zero-free intervals for roots of chromatic polynomials. We ask here whether such maximal zero-free intervals exist for σ-polynomials, and show that the only such interval is [0,∞) -- that is, the closure of the real roots of σ-polynomials is (−∞,0].
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.