Hadwiger's Conjecture for ℓ‐Link Graphs

In this article, we define and study a new family of graphs that generalizes the notions of line graphs and path graphs. Let G be a graph with no loops but possibly with parallel edges. An ?‐link of G is a walk of G of length in which consecutive edges are different. The ?‐link graph of G is the graph with vertices the ?‐links of G , such that two vertices are joined by edges in if they correspond to two subsequences of each of μ ‐links of G . By revealing a recursive structure, we bound from above the chromatic number of ?‐link graphs. As a corollary, for a given graph G and large enough ?, is 3‐colorable. By investigating the shunting of ?‐links in G , we show that the Hadwiger number of a nonempty is greater or equal to that of G . Hadwiger's conjecture states that the Hadwiger number of a graph is at least the chromatic number of that graph. The conjecture has been proved by Reed and Seymour (Eur J Combin 25(6) (2004), 873–876) for line graphs, and hence 1‐link graphs. We prove the conjecture for a wide class of ?‐link graphs.     

An approximate version of Hadwiger's conjecture for claw‐free graphs

Hadwiger's conjecture states that every graph with chromatic number χ has a clique minor of size χ. In this paper we prove a weakened version of this conjecture for the class of claw‐free graphs (graphs that do not have a vertex with three pairwise nonadjacent neighbors). Our main result is that a claw‐free graph with chromatic number χ has a clique minor of size $\lceil\frac{2}{3}\chi\rceil$. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 259–278, 2010     

Hadwiger's conjecture for quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains K_{t + 1} as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008     

On the Multichromatic Number of s‐Stable Kneser Graphs

For positive integers n and s, a subset [n] is s‐stable if for distinct . The s‐stable r‐uniform Kneser hypergraph is the r‐uniform hypergraph that has the collection of all s‐stable k‐element subsets of [n] as vertex set and whose edges are formed by the r‐tuples of disjoint s‐stable k‐element subsets of [n]. Meunier ( 21 ) conjectured that for positive integers with , and , the chromatic number of s‐stable r ‐uniform Kneser hypergraphs is equal to . It is a generalized version of the conjecture proposed by Alon et al. ( 1 ). Alon et al. ( 1 ) confirmed Meunier's conjecture for with arbitrary positive integer q. Lin et al. ( 17 ) studied the kth chromatic number of the Mycielskian of the ordinary Kneser graphs for . They conjectured that for . The case was proved by Mycielski ( 22 ). Lin et al. ( 17 ) confirmed their conjecture for , or when n is a multiple of k or . In this paper, we investigate the multichromatic number of the usual s ‐stable Kneser graphs . With the help of Fan's (1952) combinatorial lemma, we show that Meunier's conjecture is true for r is a power of 2 and s is a multiple of r, and Lin‐Liu‐Zhu's conjecture is true for .     

Bad news for chordal partitions

Reed and Seymour [1998] asked whether every graph has a partition into induced connected nonempty bipartite subgraphs such that the quotient graph is chordal. If true, this would have significant ramifications for Hadwiger's Conjecture. We prove that the answer is “no.” In fact, we show that the answer is still “no” for several relaxations of the question.     

Claw‐Free Graphs,Skeletal Graphs,and a Stronger Conjecture on ω, Δ, and χ

The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . In this article, we prove that the conjecture holds for all claw‐free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw‐free graphs with a three‐colorable complement. To prove our results, we introduce a very useful χ‐preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so‐called skeletal graphs.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

Local coloring of Kneser graphs

A local coloring of a graph G is a function c:V(G)→N having the property that for each set S⊆V(G) with 2≤|S|≤3, there exist vertices u,v∈S such that |c(u)−c(v)|≥m_S, where m_S is the number of edges of the induced subgraph 〈S〉. The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by χ_?(c). The local chromatic number of G is χ_?(G)=min{χ_?(c)}, where the minimum is taken over all local colorings c of G. The local coloring of graphs was introduced by Chartrand et al. [G. Chartrand, E. Salehi, P. Zhang, On local colorings of graphs, Congressus Numerantium 163 (2003) 207-221]. In this paper the local coloring of Kneser graphs is studied and the local chromatic number of the Kneser graph K(n,k) for some values of n and k is determined.     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008     

Schanuel's Conjecture and Algebraic Roots of Exponential Polynomials

In this article, I will prove that assuming Schanuel's conjecture, an exponential polynomial with algebraic coefficients can have only finitely many algebraic roots. Furthermore, this proof demonstrates that there are no unexpected algebraic roots of any such exponential polynomial. This implies a special case of Shapiro's conjecture: if p(x) and q(x) are two exponential polynomials with algebraic coefficients, each involving only one iteration of the exponential map, and they have common factors only of the form exp (g) for some exponential polynomial g, then p and q have only finitely many common zeros.     

On the Hadwiger's conjecture for graph products

The Hadwiger number η(G) of a graph G is the largest integer h such that the complete graph on h nodes K_h is a minor of G. Equivalently, η(G) is the largest integer such that any graph on at most η(G) nodes is a minor of G. The Hadwiger's conjecture states that for any graph G, η(G)?χ(G), where χ(G) is the chromatic number of G. It is well-known that for any connected undirected graph G, there exists a unique prime factorization with respect to Cartesian graph products. If the unique prime factorization of G is given as G₁□G₂□?□G_k, where each G_i is prime, then we say that the product dimension of G is k. Such a factorization can be computed efficiently.In this paper, we study the Hadwiger's conjecture for graphs in terms of their prime factorization. We show that the Hadwiger's conjecture is true for a graph G if the product dimension of G is at least . In fact, it is enough for G to have a connected graph M as a minor whose product dimension is at least , for G to satisfy the Hadwiger's conjecture. We show also that if a graph G is isomorphic to F^d for some F, then η(G)?χ(G)^{⌊(d-1)/2⌋}, and thus G satisfies the Hadwiger's conjecture when d?3. For sufficiently large d, our lower bound is exponentially higher than what is implied by the Hadwiger's conjecture.Our approach also yields (almost) sharp lower bounds for the Hadwiger number of well-known graph products like d-dimensional hypercubes, Hamming graphs and the d-dimensional grids. In particular, we show that for the d-dimensional hypercube H_d, . We also derive similar bounds for G^d for almost all G with n nodes and at least edges.     

Dade's Invariant Conjecture for the Symplectic Group Sp4(2 n ) and the Special Unitary Group SU4(22n ) in Defining Characteristic

In this article, we verify Dade's projective invariant conjecture for the symplectic group Sp₄(2 ⁿ ) and the special unitary group SU₄(2²ⁿ ) in the defining characteristic, that is, in characteristic 2. Furthermore, we show that the Isaacs–Malle–Navarro version of the McKay conjecture holds for Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) in the defining characteristic, that is, Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) are good for the prime 2 in the sense of Isaacs, Malle, and Navarro.     

On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>)

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K²(2k+1, k))4k when k is odd and (K²(2k+1, k))4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K²(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003