DP‐coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvořák and Postle [J. Combin. Theory Ser. B 129 (2018), pp. 38–54]. In this paper we introduce and study the fractional DP‐chromatic number . We characterize all connected graphs such that : they are precisely the graphs with no odd cycles and at most one even cycle. By a theorem of Alon, Tuza, and Voigt [Discrete Math. 165–166 (1997), pp. 31–38], the fractional list‐chromatic number of any graph equals its fractional chromatic number . This equality does not extend to fractional DP‐colorings. Moreover, we show that the difference can be arbitrarily large, and, furthermore, for every graph of maximum average degree . On the other hand, we show that this asymptotic lower bound is tight for a large class of graphs that includes all bipartite graphs as well as many graphs of high girth and high chromatic number.
Given a finite simple graph , an
 NSFPAR ID:
 10419324
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Journal of Graph Theory
 ISSN:
 03649024
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 
Abstract A graph is ‐
free if it has no induced subgraph isomorphic to , and G  denotes the number of vertices of . A conjecture of Conlon, Sudakov and the second author asserts that:For every graph , there exists such that in every ‐free graph with 
This is equivalent to:G  there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.The “sparse linear conjecture”: For every graph , there exists such that in every ‐free graph with , either some vertex has degree at least , or there are two disjoint sets of vertices, of sizes at least and , anticomplete to each other.
The sparse linear conjecture holds for all almost‐bipartite graphs .
For every almost‐bipartite graph , there exist such that for every graph with and maximum degree less than , and for every with , either contains induced copies of , or there are two disjoint sets with and , and with at most edges between them.
For every graph , there exists such that in every ‐free graph with vertices, either some vertex has degree at least , or there are two disjoint sets of vertices with , anticomplete to each other.

We design new polynomialtime algorithms for recovering planted cliques in the semirandom graph model introduced by Feige and Kilian 2001. The previous best algorithms for this model succeed if the planted clique has size at least n2/3 in a graph with n vertices (Mehta, Mckenzie, Trevisan 2019 and Charikar, Steinhardt, Valiant 2017). Our algorithms work for plantedclique sizes approaching n1/2  the informationtheoretic threshold in the semirandom model (Steinhardt 2017) and a conjectured computational threshold even in the easier fullyrandom model. This result comes close to resolving open questions by Feige 2019 and Steinhardt 2017. Our algorithms are based on higher constant degree sumofsquares relaxation and rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in unbalanced bipartite ErdősRényi random graphs into algorithms for semirandom planted clique. The use of a higherconstant degree sumofsquares is essential in our setting: we prove a lower bound on the basic SDP for certifying bicliques that shows that the basic SDP cannot succeed for planted cliques of size k=o(n2/3). We also provide some evidence that the informationcomputation tradeoff of our current algorithms may be inherent by proving an averagecase lower bound for unbalanced bicliques in the lowdegreepolynomials model.more » « less

Jurdziński, T ; Schmid, S (Ed.)In the multiparty equality problem, each of the n nodes starts with a kbit input. If there is a mismatch between the inputs, then at least one node must be able to detect it. The cost of a multiparty equality protocol is the total number of bits sent in the protocol. We consider the problem of minimizing this communication cost under the local broadcast model for the case where the underlying communication graph is undirected. In the local broadcast model of communication, a message sent by a node is received identically by all of its neighbors. This is in contrast to the classical pointtopoint communication model, where a message sent by a node to one of its neighbors is received only by its intended recipient. Under pointtopoint communication, there exists a simple protocol which is competitive within a factor 2 of the lower bound [1]. In this protocol, a rooted spanning tree is fixed and each node sends its entire input to its parent in the tree. On receiving a value from its child, a node compares it against its own input to check if the two values match. Ignoring lower order additive terms, a more complicated protocol comes within a factor 4/3 of the lower bound and is tight for certain classes of graphs [1]. Tight results, ignoring lower order terms, are also known for complete graphs [2, 9]. We study the multiparty equality problem under the local broadcast model. Recently, our work has shown that the connectivity requirements for Byzantine consensus are lower in the local broadcast model as compared to the classical model [7, 8]. In this work, 1. we identify a lower bound for the multiparty equality problem in this model. 2. we first identify simple protocols, wherein nodes are restricted to either transmit their entire input or not transmit anything at all, and find that these can cost Ω(logn) times the lower bound using existing example for the set cover problem [12]. 3. we then design a protocol to solve the problem within a constant factor of the lower bound.more » « less

We consider how to generate graphs of arbitrary size whose chromatic numbers can be chosen (or are wellbounded) for testing graph coloring algorithms on parallel computers. For the distance1 graph coloring problem, we identify three classes of graphs with this property. The first is the ErdősRényi random graph with prescribed expected degree, where the chromatic number is known with high probability. It is also known that the Greedy algorithm colors this graph using at most twice the number of colors as the chromatic number. The second is a random geometric graph embedded in hyperbolic space where the size of the maximum clique provides a tight lower bound on the chromatic number. The third is a deterministic graph described by Mycielski, where the graph is recursively constructed such that its chromatic number is known and increases with graph size, although the size of the maximum clique remains two. For Jacobian estimation, we bound the distance2 chromatic number of random bipartite graphs by considering its equivalence to distance1 coloring of an intersection graph. We use a “balls and bins” probabilistic analysis to establish a lower bound and an upper bound on the distance2 chromatic number. The regimes of graph sizes and probabilities that we consider are chosen to suit the Jacobian estimation problem, where the number of columns and rows are asymptotically nearly equal, and have number of nonzeros linearly related to the number of columns. Computationally we verify the theoretical predictions and show that the graphs are often be colored optimally by the serial and parallel Greedy algorithms.more » « less