Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe energy of C4-free graphs of bounded degree
356
0
0.0
(
0
)
Authors
Vladimir Nikiforov
Ask ChatGPT about the research
No Arabic abstract
Answering some questions of Gutman, we show that, except for four specific trees, every connected graph G of order n, with no cycle of order 4 and with maximum degree at most 3, has energy greater that its order. Here, the energy of a graph is the sum of the moduli of its eigenvalues. We give more general theorems and state two conjectures.
rate research
Read More
Motivated by a longstanding conjecture of Thomassen, we study how large the average degree of a graph needs to be to imply that it contains a $C_4$-free subgraph with average degree at least $t$. Kuhn and Osthus showed that an average degree bound which is double exponential in t is sufficient. We give a short proof of this bound, before reducing it to a single exponential. That is, we show that any graph $G$ with average degree at least $2^{ct^2log t}$ (for some constant $c>0$) contains a $C_4$-free subgraph with average degree at least $t$. Finally, we give a construction which improves the lower bound for this problem, showing that this initial average degree must be at least $t^{3-o(1)}$.
A (not necessarily proper) vertex colouring of a graph has clustering $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $Delta$ are 3-colourable with clustering $O(Delta^2)$. The previous best bound was $O(Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $Delta$ that exclude a fixed minor are 3-colourable with clustering $O(Delta^5)$. The best previous bound for this result was exponential in $Delta$.
For a graph $G=(V,E)$, $kin mathbb{N}$, and a complex number $w$ the partition function of the univariate Potts model is defined as [ {bf Z}(G;k,w):=sum_{phi:Vto [k]}prod_{substack{uvin E phi(u)=phi(v)}}w, ] where $[k]:={1,ldots,k}$. In this paper we give zero-free regions for the partition function of the anti-ferromagnetic Potts model on bounded degree graphs. In particular we show that for any $Deltain mathbb{N}$ and any $kgeq eDelta+1$, there exists an open set $U$ in the complex plane that contains the interval $[0,1)$ such that ${bf Z}(G;k,w) eq 0$ for any $win U$ and any graph $G$ of maximum degree at most $Delta$. (Here $e$ denotes the base of the natural logarithm.) For small values of $Delta$ we are able to give better results. As an application of our results we obtain improved bounds on $k$ for the existence of deterministic approximation algorithms for counting the number of proper $k$-colourings of graphs of small maximum degree.
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all $k$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of the $(ktimes k)$-wall or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For $tgeq 2$, a $t$-theta is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least $t$. A $t$-pyramid is a graph consisting of a vertex $v$, a triangle $B$ disjoint from $v$ and three paths starting at $v$ and disjoint otherwise, each joining $v$ to a vertex of $B$, and each of length at least $t$. We prove that for all $k,t$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a $t$-theta, or a $t$-pyramid, or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a $t$-theta for some $tgeq 2$). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every $Delta$ and subcubic subdivided caterpillar $T$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of $T$ or the line graph of a subdivision of $T$ as an induced subgraph.
In this work we present a new local to global criterion for proving a form of high dimensional expansion, which we term cosystolic expansion. Applying this criterion on Ramanujan complexes, yields for every dimension, an infinite family of bounded degree complexes with the topological overlapping property. This answer affirmatively an open question raised by Gromov.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
