A graph where each vertex v has a list L(v) of available colors is L-colorable if there is a proper coloring such that the color of v is in L(v) for each v. A graph is k-choosable if every assignment L of at least k colors to each vertex guarantees an L-coloring. Given a list assignment L, an L-request for a vertex v is a color c∈L(v). In this paper, we look at a variant of the widely studied class of precoloring extension problems from Dvořák, Norin, and Postle (J. Graph Theory, 2019), wherein one must satisfy “enough”, as opposed to all, of the requested set of precolors. A graph G is ɛ-flexible for list size k if for any k-list assignment L, and any set S of L-requests, there is an L-coloring of G satisfying ɛ-fraction of the requests in S. It is conjectured that planar graphs are ɛ-flexible for list size 5, yet it is proved only for list size 6 and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masařík and show that planar graphs without K4− are ɛ-flexible for list size 5. We also prove that planar graphs without 4-cycles and 3-cycle distance at least 2 are ɛ-flexible for list size 4. Finally, we introduce a new (slightly weaker) form of ɛ-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are ɛ-flexible for list size 5.

The study of positive solutions of the heat equation $\frac{\partial}{\partial \alpha} u = \Delta u$, on both manifolds and graphs, gives an analytic way of extracting geometric information about the object. In the manifold case, one of the most effective ways of studying how solutions to the heat equation evolve is to derive a local “gradient estimate” of heat change, using curvature lower bounds. Recently, notions of curvature for graphs have been developed which enable proving similar estimates for graphs. In this article, we derive a gradient estimate for positive heat solutions that considers only how heat varies in space and the time derivative. This result, due in the manifold case to Hamilton, applies to both finite graphs and infinite graphs of bounded degree. As a corollary, a heat comparison theorem is also developed. This in turn yields results about the mixing of the continuous time random walk on graphs.

This study considers the soft capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph G=(V,E), which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex v in the cover, the number of v's incident edges covered by the copy is up to a given capacity of v. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with O(log n / epsilon) amortized update time, where n is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a non-uniform and unsplittable demand, and (2) the more general capacitated set cover problem.

We establish mild conditions under which a possibly irregular, sparse graph $G$ has “many” strong orientations. Given a graph $G$ on $n$ vertices, orient each edge in either direction with probability $1/2$ independently. We show that if $G$ satisfies a minimum degree condition of $(1+c_1)\log_2{n}$ and has Cheeger constant at least $c_2\frac{\log_2\log_2{n}}{\log_2{n}}$, then the resulting randomly oriented directed graph is strongly connected with high probability. This Cheeger constant bound can be replaced by an analogous spectral condition via the Cheeger inequality. Additionally, we provide an explicit construction to show our minimum degree condition is tight while the Cheeger constant bound is tight up to a $\log_2\log_2{n}$ factor.

A classical result of Hajnal and Szemerédi, when translated to a complementary form, states that with sufficient minimum degree, a graph will contain disjoint large cliques. We conjecture a generalization of this result from cliques to cycles with many chords and prove this conjecture in several cases.

In this paper we consider an extremal problem regarding multigraphs with edge multiplicity bounded by a positive integer $q$. Given a family $\mathscr{F}$ of $q$-multigraphs, define $ex(n,\mathscr{F})$ to be the maximum number of edges (counting multiplicities) that a $q$-multigraph on $n$ vertices can have without containing a copy of any $F \in \mathscr{F}$ (not necessarily induced). It is well known that $\tau(\mathscr{F}) = \lim_{n \to \infty} ex(n,\mathscr{F})/\binom{n}{2}$ exists for every family $\mathscr{F}$ (finite or infinite). Let $\mathscr{T} = \{\tau(\mathscr{F}) : \mathscr{F} \textrm{ is a family of $q$-multigraphs}\}$. We say the number $\alpha$, $0 \leq \alpha < q$, is a jump for $q$ if there exists a constant $c = c(\alpha,q)$ such that if $\alpha' \in \mathscr{T}$ such that $\alpha' > \alpha$, then $\alpha' \geq \alpha + c$. The Erdös--Stone theorem implies that for $q=1$, every $\alpha \in [0,1)$ is a jump. The problem of determining the set of jumps for $q \geq 2$ appears to be much harder. In a sequence of papers by Erdös, Brown, and Simonovits and, separately, Sidorenko, the authors established that every $\alpha$ is a jump for $q=2$, leaving the question of whether the same is true for $q \geq 3$ unresolved. A later result of Rödl and Sidorenko [V. Rödl and A. Sidorenko, J. Combin. Theory Ser. A, 69 (1995), pp. 347--357] gave a negative answer establishing that for $q \geq 4$ some values of $\alpha$ are not jumps. The problem of whether or not every $\alpha \in [0,3)$ is a jump for $q=3$ has remained open. We give a partial positive result in this paper proving that every $\alpha \in [0,2)$ is a jump for all $q \geq 3$. Additionally, we extend the results of Rödl and Sidorenko by showing, given any rational number $r$ with $0

It has been observed that individuals' decisions to adopt a product or innovation are often influenced by the recommendations of their friends and acquaintances. Motivated by this observation, the last few years have seen a number of studies on influence maximization in social networks. The primary goal of these studies is identification of k most influential nodes in a network. A major limitation of these studies is that they focus on a non-adversarial environment, where only one player is engaged in influencing the nodes. However, in a realistic scenario multiple players attempt to influence the nodes in a competitive fashion. The proposed model considers a competitive environment where a node that has not yet adopted an innovation, can adopt only one of the several competing innovations and once it adopts an innovation, it does not switch. The paper studies the scenario where the first player has already chosen a set of k nodes and the second player, with the knowledge of the choice of the first, attempts to identify a smallest set of nodes (excluding the ones already chosen by the first) so that when the influence propagation process ends, the number of nodes influenced by the second player is larger than the number of nodes influenced by the first.