On 3-colorable non-4-choosable planar graphs

An L-list coloring of a graph G is a proper vertex coloring in which every vertex v gets a color from a list L(v) of allowed colors. G is called k-choosable if all lists L(v) have exactly k elements and if G is L-list colorable for all possible assignments of such lists. Verifying conjectures of Erdos, Rubin and Taylor it was shown during the last years that every planar graph is 5-choosable and that there are planar graphs which are not 4-choosable. The question whether there are 3-colorable planar graphs which are not 4-choosable remained unsolved. The smallest known example far a non-4-choosable planar graph has 75 vertices and is described by Gutner. In fact, this graph is also 3 colorable and answers the above question. In addition, we give a list assignment for this graph using 5 colors only in all of the lists together such that the graph is not List-colorable. © 1997 John Wiley & Sons, Inc.     

On 3-colorable planar graphs without prescribed cycles

In this paper we prove that every planar graph without cycles of length 4, 5, 6 and 8 is 3-colorable.     

A counterexample to the bold conjecture

A pair of vertices (x,y) of a graph G is an o-critical pair if o(G + xy) > o(G), where G + xy denotes the graph obtained by adding the edge xy to G and o(H) is the clique number of H. The o-critical pairs are never edges in G. A maximal stable set S of G is called a forced color class of G if S meets every o-clique of G, and o-critical pairs within S form a connected graph. In 1993, G. Bacsó raised the following conjecture which implies the famous Strong Perfect Graph Conjecture: If G is a uniquely o-colorable perfect graph, then G has at least one forced color class. This conjecture is called the Bold Conjecture. Here we show a simple counterexample to it. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 165–168, 1997     

A counterexample to the rank-coloring conjecture

It has been conjectured by C. van Nuffelen that the chromatic number of any graph with at least one edge does not exceed the rank of its adjacency matrix. We give a counterexample, with chromatic number 32 and with an adjacency matrix of rank 29.     

A counterexample to the triangle conjecture

The triangle conjecture sets a bound on the cardinality of a code formed by words of the form aⁱba^j. A counterexample exceeding that bound is given. This also disproves a stronger conjecture that every code is commutatively equivalent to a prefix code.     

A counterexample to Wood's conjecture

We prove that if the one-point compactification of a locally compact, noncompact Hausdorff space L is the topological space called pseudoarc, then C₀(L,C) is almost transitive. We also obtain two necessary conditions on a metrizable locally compact Hausdorff space L for C₀(L) being almost transitive.     

A counterexample to the ``composition conjecture"

In this note we construct a class of counterexamples to the ``composition conjecture" concerning an infinitesimal version of the center problem for the polynomial Abel equation in the complex domain.

     

A volume-preserving counterexample to the Seifert conjecture

We prove that every 3-manifold possesses aC ¹, volume-preserving flow with no fixed points and no closed trajectories. The main construction is a volume-preserving version of the Schweitzer plug. We also prove that every 3-manifold possesses a volume-preserving,C ^∞ flow with discrete closed trajectories and no fixed points (as well as a PL flow with the same geometry), which is needed for the first result. The proof uses a Dehn-twisted Wilson-type plug which also preserves volume. The author was supported by an NSF Postdoctoral Fellowship, grant #DMS-9107908.     

A simple counterexample to the Hambleton-Taylor-Williams conjecture

It is shown that the conjectured formula of Hambleton, Taylor, and Williams for theG-theory of the integral group ring of a finite group does not hold for the symmetric groupsS ₅.     

A counterexample to the finite height conjecture

There is an infinite subdirectly irreducible lattice which generates a variety that contains only finitely many subvarietes.The author was supported in part by NSF Grant DMS 94-00511     

A counterexample to the bipartizing matching conjecture

The bipartizing matching conjecture (BMC) is a rather new approach to the nowhere zero 5-flow conjecture (NZ5FC) and the cycle double cover conjecture (CDCC). We show that the BMC is wrong in its actual version by constructing a counterexample. The construction arises from the investigation of the problem to cover the vertices of a graph by two induced Eulerian subgraphs. Finally, we state a modified version of the BMC which has the same impact on the NZ5FC and CDCC.     

A counterexample to the dominating set conjecture

The metric polytope met _n is the polyhedron associated with all semimetrics on n nodes and defined by the triangle inequalities x _ij − x _ik − x _jk ≤ 0 and x _ij + x _ik + x _jk ≤ 2 for all triples i, j, k of {1,..., n}. In 1992 Monique Laurent and Svatopluk Poljak conjectured that every fractional vertex of the metric polytope is adjacent to some integral vertex. The conjecture holds for n ≤ 8 and, in particular, for the 1,550,825,600 vertices of met₈. While the overwhelming majority of the known vertices of met₉ satisfy the conjecture, we exhibit a fractional vertex not adjacent to any integral vertex.     

A counterexample to the DeMarco‐Kahn upper tail conjecture

Given a fixed graph H, what is the (exponentially small) probability that the number X_H of copies of H in the binomial random graph G_n,p is at least twice its mean? Studied intensively since the mid 1990s, this so‐called infamous upper tail problem remains a challenging testbed for concentration inequalities. In 2011 DeMarco and Kahn formulated an intriguing conjecture about the exponential rate of decay of  for fixed ε > 0. We show that this upper tail conjecture is false, by exhibiting an infinite family of graphs violating the conjectured bound.     

A counterexample to kippenhahn's conjecture on hermitian pencils

A counterexample is constructed to a conjecture of Kippenhahn (Math. Nachr. 6:193–288 (1951–52)). A pair of Hermitian 8×8 matrices H, K is found such that (1) H, K generate $\text{M}{}_8\text{(}\text{C}\text{)}$ and (2) the minimal polynomial of the pencil xH + yK has degree 4. Recent work of H. Shapiro [e.g. Linear Algebra Appl. 43:201–221 (1982)] has established the conjecture for n×n matrices n?5.     

A counterexample to a conjecture of Friedland

This paper is concerned with a conjecture of Friedland [S. Friedland, Rational orthogonal similarity of rational symmetric matrices, Linear Algebra Appl. 192 (1993) 109–114]. A method for constructing counterexamples to the above conjecture is provided.     

A counterexample to the Alon-Saks-Seymour conjecture and related problems

Consider a graph obtained by taking an edge disjoint union of k complete bipartite graphs. Alon, Saks, and Seymour conjectured that such graphs have chromatic number at most k+1. This well known conjecture remained open for almost twenty years. In this paper, we construct a counterexample to this conjecture and discuss several related problems in combinatorial geometry and communication complexity.