Minimal orientations of colour critical graphs

In 1966 T. Gallai asked whether every criticalk-chromatic graph possesses an orientation having just one directed path of lengthk–1. In this note we show that in general the answer is negative, but also that the answer is affirmative whenk5 and the graph has maximal degree at mostk.     

Minimal imperfect graphs: A simple approach

We provide a very short proof of the following theorem of Lovász, and of its consequences:A graph is perfect if and only if in every induced subgraph the number of vertices does not exceed the product of the stability and clique numbers of the subgraph.This proof is conceptually new: it does not use the replication operation, or any kind of polyhedral argument; the arguments resemble more the well-known ways of deducing structural properties of minimal imperfect graphs. However, the known proofs of these structural properties use Lovász's result, whereas the present work leads to a proof of Lovász's result itself, and actually to a slight sharpening.The author gratefully acknowledges financial support from Ministère de la Recherche et de la Technologie (the French Ministry of Research and Technology, MRT) which sponsored his three month visit to Laboratory ARTEMIS of Grenoble University which motivated him to do this work.     

H-extension of graphs

We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included.     

Minimal generators of toric ideals of graphs

Let IG be the toric ideal of a graph G. We characterize in graph theoretical terms the primitive, the minimal, the indispensable and the fundamental binomials of the toric ideal IG.     

On well-quasi-ordering-finite graphs by immersion

It has been conjectured by Nash-Williams that the class of all graphs is well-quasi-ordered under the quasi-order ≦ defined by immersion. Two partial results are proved which support this conjecture. (i) The class of finite simple graphsG with K _2,3 is well-quasi-ordered by ≦, (ii) it is shown that a class of finite graphs is well-quasi-ordered by ≦ provided that the blocks of its members satisfy certain restrictive conditions. (In particular, this second result implies that ≦ is a well-quasi-order on the class of graphs for which each block is either complete or a cycle.)     

Regular odd rings and non-planar graphs

In a previous paper we have announced that a graph is non-planar if and only if it contains a maximal, strict, compact, odd ring. Little has conjectured that the compactness condition may be removed. Chernyak has now published a proof of this conjecture. However, it is difficult to test a ring for maximality. In this paper we show that for odd rings of size five or greater, the condition of maximality may be replaced by a new one called regularity. Regularity is an easier condition to diagnose than is maximality.     

Packing paths in planar graphs

A generalization of P. Seymour's theorem on planar integral 2-commodity flows is given when the underlying graphG together with the demand graphH (a graph having edges that connect the corresponding terminal pairs) form a planar graph and the demand edges are on two faces ofG.     

How not to characterize planar-emulable graphs

We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph)—a problem raised already in Fellows? thesis (1985) and conceptually related to the better known planar cover conjecture by Negami (1986). For over two decades, the planar emulator problem lived poorly in a shadow of Negami?s conjecture—which is still open—as the two were considered equivalent. But, at the end of 2008, a surprising construction by Rieck and Yamashita falsified the natural “planar emulator conjecture”, and thus opened a whole new research field. We present further results and constructions which show how far the planar-emulability concept is from planar-coverability, and that the traditional idea of likening it to projective embeddability is actually very out-of-place. We also present several positive partial characterizations of planar-emulable graphs.     

Nonexistence of universal graphs without some trees

IfG is a finite tree with a unique vertex of largest, and 4 degree which is adjacent to a leaf then there is no universal countableG-free graph.Research partially supported by the Hungarian Science Research Grant OTKA No. 2117 and by the European Communities (Cooperation in Science and Technology with Central and Eastern European Countries) contract number ERBCIPACT930113.     

Geometric graphs with no two parallel edges

We give a simple proof for a theorem of Katchalski, Last, and Valtr, asserting that the maximum number of edges in a geometric graph G on n vertices with no pair of parallel edges is at most 2n−2. We also give a strengthening of this result in the case where G does not contain a cycle of length 4. In the latter case we show that G has at most 3/2(n−1) edges.     

The complexity of a class of infinite graphs

IfG _k is the family of countable graphs with nok vertex (or edge) disjoint circuits (1<k<) then there is a countableG _k G _k such that every member ofG _k is an (induced) subgraph of some member ofG _k , but no finiteG _k suffices.     

On automorphisms of infinite graphs with forbidden subgraphs

LexX be anm-connected infinite graph without subgraphs homeomorphic toKm, n, for somen, and let α be an automorphism ofX with at least one cycle of infinite length. We characterize the structure of α and use this characterization to extend a known result about orientation-preserving automorphisms of finite plane graphs to infinite plane graphs. In the last section we investigate the action of α on the ends ofX and show that α fixes at most two ends (Theorem 3.2).     

Fractionally colouring total graphs

Bchzad and Vizing have conjectured that given any simple graph of maximum degree , one can colour its edges and vertices with +2 colours so that no two adjacent vertices, or two incident edges, or an edge and either of its ends receive the same colour. We show that for any simple graphG, V(G)E(G) can be fractionally coloured with +2 colours.     

Minimum cycle bases of graphs on surfaces

In this paper we study the cycle base structures of embedded graphs on surfaces. We first give a sufficient and necessary condition for a set of facial cycles to be contained in a minimum cycle base (or MCB in short) and then set up a 1-1 correspondence between the set of MCBs and the set of collections of nonseparating cycles which are in general positions on surfaces and are of shortest total length. This provides a way to enumerate MCBs in a graph via nonseparating cycles. In particular, some known results such as P.F. Stadler's work on Halin graphs [Minimum cycle bases of Halin graphs, J. Graph Theory 43 (2003) 150-155] and Leydold and Stadler's results on outer-planar graphs [Minimum cycle bases of outerplanar graphs, Electronic J. Combin. 5(16) (1998) 14] are concluded. As applications, the number of MCBs in some types of graphs embedded in lower surfaces (with arbitrarily high genera) is found. Finally, we present an interpolation theorem for the number of one-sided cycles contained in MCB of an embedded graph.     

Minimal Bar Tableaux

Motivated by recent results of Stanley, we generalize the rank of a partition λ to the rank of a shifted partition S(λ). We show that the number of bars required in a minimal bar tableau of S(λ) is max(o, e + (ℓ(λ) mod 2)), where o and e are the number of odd and even rows of λ. As a consequence we show that the irreducible projective characters of S_n vanish on certain conjugacy classes. Another corollary is a lower bound on the degree of the terms in the expansion of Schur’s Q_λ symmetric functions in terms of the power sum symmetric functions. Received November 20, 2003     

Planar graphs and poset dimension

We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<_G b if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V E whose intersection is <_G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning.     

Planar acyclic oriented graphs

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.     

Uniqueness and minimality of large face-width embeddings of graphs

LetG be a graph embedded in a surface of genusg. It is shown that if the face-width of the embedding is at leastclog(g)/loglog(g), then such an embedding is unique up to Whitney equivalence. If the face-width is at leastclog(g), then every embedding ofG which is not Whitney equivalent to our embedding has strictly smaller Euler characteristic.Supported in part by the Ministry of Science and Technology of Slovenia, Research Project P1-0210-101-94.     

Small cycle double covers of 4-connected planar graphs

Acycle double cover of a graph,G, is a collection of cycles,C, such that every edge ofG lies in precisely two cycles ofC. TheSmall Cycle Double Cover Conjecture, proposed by J. A. Bondy, asserts that every simple bridgeless graph onn vertices has a cycle double cover with at mostn–1 cycles, and is a strengthening of the well-knownCycle Double Cover Conjecture. In this paper, we prove Bondy's conjecture for 4-connected planar graphs.