Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOccupancy fraction, fractional colouring, and triangle fraction
69
0
0.0
(
0
)
Added by
Fran\\c{c}ois Pirot
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given $varepsilon>0$, there exists $f_0$ such that, if $f_0 le f le Delta^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $Delta$ in which the neighbourhood of every vertex in $G$ spans at most $Delta^2/f$ edges, (i) an independent set of $G$ drawn uniformly at random has at least $(1/2-varepsilon)(n/Delta)log f$ vertices in expectation, and (ii) the fractional chromatic number of $G$ is at most $(2+varepsilon)Delta/log f$. These bounds cannot in general be improved by more than a factor $2$ asymptotically. One may view these as strong
rate research
Read More
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? We answer this question in the affirmative for triangle-free graphs.
This paper provides a survey of methods, results, and open problems on graph and hypergraph colourings, with a particular emphasis on semi-random `nibble methods. We also give a detailed sketch of some aspects of the recent proof of the ErdH{o}s-Faber-Lov{a}sz conjecture.
Switches are operations which make local changes to the edges of a graph, usually with the aim of preserving the vertex degrees. We study a restricted set of switches, called triangle switches. Each triangle switch creates or deletes at least one triangle. Triangle switches can be used to define Markov chains which generate graphs with a given degree sequence and with many more triangles (3-cycles) than is typical in a uniformly random graph with the same degrees. We show that the set of triangle switches connects the set of all $d$-regular graphs on $n$ vertices, for all $dgeq 3$. Hence, any Markov chain which assigns positive probability to all triangle switches is irreducible on these graphs. We also investigate this question for 2-regular graphs.
An orientation of $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation emph{proper} if neighbouring vertices have different in-degrees. The proper orientation number of a graph $G$, denoted by $vec{chi}(G)$, is the minimum maximum in-degree of a proper orientation of G. Araujo et al. (Theor. Comput. Sci. 639 (2016) 14--25) asked whether there is a constant $c$ such that $vec{chi}(G)leq c$ for every outerplanar graph $G$ and showed that $vec{chi}(G)leq 7$ for every cactus $G.$ We prove that $vec{chi}(G)leq 3$ if $G$ is a triangle-free $2$-connected outerplanar graph and $vec{chi}(G)leq 4$ if $G$ is a triangle-free bridgeless outerplanar graph.
The Ising antiferromagnet is an important statistical physics model with close connections to the {sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry breaking phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the {sc Max Cut} of random regular graphs predicted by Zdeborova and Boettcher [Journal of Statistical Mechanics 2010]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten-Stigum bound.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
