An official website of the United States government
We consider how to generate graphs of arbitrary size whose chromatic numbers can be chosen (or are well-bounded) for testing graph coloring algorithms on parallel computers. For the distance-1 graph coloring problem, we identify three classes of graphs with this property. The first is the Erdős-Ré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 distance-2 chromatic number of random bipartite graphs by considering its equivalence to distance-1 coloring of an intersection graph. We use a “balls and bins” probabilistic analysis to establish a lower bound and an upper bound on the distance-2 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
The jump of the clique chromatic number of random graphs
Abstract The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In 2016 McDiarmid, Mitsche and Prałat noted that around the clique chromatic number of the random graph changes by when we increase the edge‐probability by , but left the details of this surprising “jump” phenomenon as an open problem. We settle this problem, that is, resolve the nature of this polynomial “jump” of the clique chromatic number of the random graph around edge‐probability . Our proof uses a mix of approximation and concentration arguments, which enables us to (i) go beyond Janson's inequality used in previous work and (ii) determine the clique chromatic number of up to logarithmic factors for any edge‐probability .
more »
« less
- PAR ID:
- 10419793
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 62
- Issue:
- 4
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 1016-1034
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an Erdős‐Rényi random graph exceeds its expectation by some constant factor. There has been much exciting recent progress on this problem. We study the corresponding problem for hypergraphs, for which less is known about the large deviation rate. We present new phenomena in upper tail large deviations for sparse random hypergraphs that are not seen in random graphs. We conjecture a formula for the large deviation rate, that is, the first order asymptotics of the log‐probability that the number of copies of fixed subgraphHin a sparse Erdős‐Rényi randomk‐uniform hypergraph exceeds its expectation by a constant factor. This conjecture turns out to be significantly more intricate compared to the case for graphs. We verify our conjecture when the fixed subgraphHbeing counted is a clique, as well as whenHis the 3‐uniform 6‐vertex 4‐edge hypergraph consisting of alternating faces of an octahedron, where new techniques are required.more » « less
-
null (Ed.)We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique. Specifically, let $$G \sim G(n,1/2,k)$$ be a random graph on $$n$$ vertices with a planted clique of size $$k$$. We show that no algorithm that makes at most $q = o(n^2 / k^2 + n)$ adaptive queries to the adjacency matrix of $$G$$ is likely to find the planted clique. On the other hand, when $$k \geq (2+\epsilon) \log_2 n$$ there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making $$q = O( (n^2 / k^2) \log^2 n + n \log n)$$ adaptive queries. For detection, the additive $$n$$ term is not necessary: the number of queries needed to detect the presence of a planted clique is $n^2 / k^2$ (up to logarithmic factors).more » « less
-
Aichholzer, Oswin; Wang, Haitao (Ed.)A graph is said to contain K_k (a clique of size k) as a weak immersion if it has k vertices, pairwise connected by edge-disjoint paths. In 1989, Lescure and Meyniel made the following conjecture related to Hadwiger’s conjecture: Every graph of chromatic number k contains K_k as a weak immersion. We prove this conjecture for graphs with at most 1.4(k-1) vertices. As an application, we make some progress on Albertson’s conjecture on crossing numbers of graphs, according to which every graph G with chromatic number k satisfies cr(G) ≥ cr(K_k). In particular, we show that the conjecture is true for all graphs of chromatic number k, provided that they have at most 1.4(k-1) vertices and k is sufficiently large.more » « less
-
Abstract Aholein a graph is an induced cycle of length at least four, and a ‐multiholein is the union of pairwise disjoint and nonneighbouring holes. It is well known that if does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any integer , if does not contain a ‐multihole, then its chromatic number is at most a polynomial function of its clique number. We show that the same result holds if we ask for all the holes to be odd or of length four; and if we ask for the holes to be longer than any fixed constant or of length four. This is part of a broader study of graph classes that are polynomially ‐bounded.more » « less
