A graph
Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles
If
- PAR ID:
- 10039852
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 87
- Issue:
- 4
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- p. 660-671
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract G is said to be 2‐divisible if for all (nonempty) induced subgraphsH ofG ,can be partitioned into two sets such that and . (Here denotes the clique number of G , the number of vertices in a largest clique ofG ). A graphG is said to be perfectly divisible if for all induced subgraphsH ofG ,can be partitioned into two sets such that is perfect and . We prove that if a graph is ‐free, then it is 2‐divisible. We also prove that if a graph is bull‐free and either odd‐hole‐free or P 5‐free, then it is perfectly divisible. -
more » « less
Abstract Let
be integers with , and set . Erdős proved that when , each n ‐vertex nonhamiltonian graphG with minimum degreehas at most edges. He also provides a sharpness example for all such pairs . Previously, we showed a stability version of this result: for n large enough, every nonhamiltonian graphG onn vertices withand more than edges is a subgraph of . In this article, we show that not only does the graph maximize the number of edges among nonhamiltonian graphs with n vertices and minimum degree at leastd , but in fact it maximizes the number of copies of any fixed graphF whenn is sufficiently large in comparison withd and. We also show a stronger stability theorem, that is, we classify all nonhamiltonian n ‐vertex graphs withand more than edges. We show this by proving a more general theorem: we describe all such graphs with more than copies of for any k . -
more » « less
Abstract It is proved that for every countable structure
and a computable successor ordinal α there is a countable structure which is ‐least among all countable structures such that is Σ‐definable in the αth jump . We also show that this result does not hold for the limit ordinal . Moreover, we prove that there is no countable structure with the degree spectrum for . -
more » « less
Abstract In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs on
with m edges, whenever and . We give an asymptotic formula for the number of connected r‐uniform hypergraphs on with m edges, whenever is fixed and with , that is, the average degree tends to infinity. This complements recent results of Behrisch, Coja‐Oghlan, and Kang (the case ) and the present authors (the case , ie, “nullity” or “excess” o (n )). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use “smoothing” techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem. -
more » « less
Abstract Given a graph
, its auxiliary square‐graph is the graph whose vertices are the non‐edges of and whose edges are the pairs of non‐edges which induce a square (i.e., a 4‐cycle) in . We determine the threshold edge‐probability at which the Erdős–Rényi random graph begins to asymptotically almost surely (a.a.s.) have a square‐graph with a connected component whose squares together cover all the vertices of . We show , a polylogarithmic improvement on earlier bounds on due to Hagen and the authors. As a corollary, we determine the threshold at which the random right‐angled Coxeter group a.a.s. becomes strongly algebraically thick of order 1 and has quadratic divergence.
