Large minors in graphs with given independence number

A weakening of Hadwiger’s conjecture states that every n-vertex graph with independence number α has a clique minor of size at least . Extending ideas of Fox (2010) [6], we prove that such a graph has a clique minor with at least vertices where c>1/19.2.     

Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of over all subgraphs H with at least two vertices. Generalizing the Nash‐Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if , then G decomposes into forests with one having maximum degree at most d. The conjecture was previously proved for ; we prove it for and when and . For , we can further restrict one forest to have at most two edges in each component. For general , we prove weaker conclusions. If , then implies that G decomposes into k forests plus a multigraph (not necessarily a forest) with maximum degree at most d. If , then implies that G decomposes into forests, one having maximum degree at most d. Our results generalize earlier results about decomposition of sparse planar graphs.     

Packing chromatic number of cubic graphs

A packing$k$-coloring of a graph $G$ is a partition of $V\left(G\right)$ into sets $V_1,\dots ,V_k$ such that for each $1\le i\le k$ the distance between any two distinct $x,y\in V_i$ is at least $i+1$. The packing chromatic number, ${\chi }_p\left(G\right)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. Sloper showed that there are $4$-regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed $k$ and $g\ge 2k+2$, almost every $n$-vertex cubic graph of girth at least $g$ has the packing chromatic number greater than $k$.     

Equitable versus nearly equitable coloring and the Chen-Lih-Wu conjecture

Chen, Lih, and Wu conjectured that for r ≥ 3, the only connected graphs with maximum degree at most r that are not equitably r-colorable are K _r,r (for odd r) and K _r+1. If true, this would be a strengthening of the Hajnal-Szemerédi Theorem and Brooks’ Theorem. We extend their conjecture to disconnected graphs. For r ≥ 6 the conjecture says the following: If an r-colorable graph G with maximum degree r is not equitably r-colorable then r is odd, G contains K _r,r and V(G) partitions into subsets V ₀, …, V _t such that G[V ₀] = K _r,r and for each 1 ≤ i ≤ t, G[V _i ] = K _r . We characterize graphs satisfying the conclusion of our conjecture for all r and use the characterization to prove that the two conjectures are equivalent. This new conjecture may help to prove the Chen-Lih-Wu Conjecture by induction.     

The dimension of suborders of the Boolean lattice

We consider the order dimension of suborders of the Boolean latticeB _n . In particular we show that the suborder consisting of the middle two levels ofB _n dimension at most of 6 log₃ n. More generally, we show that the suborder consisting of levelss ands+k ofB _n has dimensionO(k ² logn).The research of the second author was supported by Office of Naval Research Grant N00014-90-J-1206.The research of the third author was supported by Grant 93-011-1486 of the Russian Fundamental Research Foundation.     

Photochemical oxidation of 1,2,2,6,6-pentamethyl-4-piperidol by ketones

Chemistry of Heterocyclic Compounds -     

On graphs with small Ramsey numbers*

Let R(G) denote the minimum integer N such that for every bicoloring of the edges of K_N, at least one of the monochromatic subgraphs contains G as a subgraph. We show that for every positive integer d and each γ,0 < γ < 1, there exists k = k(d,γ) such that for every bipartite graph G = (W,U;E) with the maximum degree of vertices in W at most d and , . This answers a question of Trotter. We give also a weaker bound on the Ramsey numbers of graphs whose set of vertices of degree at least d + 1 is independent. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 198–204, 2001     

Estimating the Minimal Number of Colors in Acyclic $$k $$ -Strong Colorings of Maps on Surfaces

A coloring of the vertices of a graph is called acyclic if the ends of each edge are colored in distinct colors, and there are no two-colored cycles. Suppose each face of rank $k$ , $k \geqslant 4$ , in a map on a surface $S^N $ is replaced by the clique having the same number of vertices. It is proved in [1] that the resulting pseudograph admits an acyclic coloring with the number of colors depending linearly on N and $k$ . In the present paper we prove a sharper estimate $55( - Nk)^{4/7} $ for the number of colors provided that $k \geqslant 1$ and $ - N \geqslant 5^7 k^{4/3} $ .     

A list analogue of equitable coloring

Given lists of available colors assigned to the vertices of a graph G, a list coloring is a proper coloring of G such that the color on each vertex is chosen from its list. If the lists all have size k, then a list coloring is equitable if each color appears on at most vertices. A graph is equitably k-choosable if such a coloring exists whenever the lists all have size k. We prove that G is equitably k-choosable when unless G contains or k is odd and . For forests, the threshold improves to . If G is a 2-degenerate graph (given k ≥ 5) or a connected interval graph (other than ), then G is equitably k-choosable when . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 166–177, 2003