Antisymmetric flows on planar graphs

We prove that every oriented planar graph admits a homomorphism to the Paley tournament P₂₇₁ and hence that every oriented planar graph has an antisymmetric flow number and a strong oriented chromatic number of at most 271. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 200–210, 2006     

Constructing isospectral non‐isomorphic digraphs from hypergraphs

We explore the “oriented line graph” construction associated with a hypergraph, leading to a construction of pairs of strongly connected directed graphs whose adjacency operators have the same spectra. We give conditions on a hypergraph so that a hypergraph and its dual give rise to isospectral, but non‐isomorphic, directed graphs. The proof of isospectrality comes from an argument centered around hypergraph zeta functions as defined by Storm. To prove non‐isomorphism, we establish a Whitney‐type result by showing that the oriented line graphs are isomorphic if and only if the hypergraphs are. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 231–242, 2010     

Homomorphism bounds for oriented planar graphs

If is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a homomorphism bound for if there is a homomorphism from each graph in to H. We find some necessary conditions for a graph to be a homomorphism bound for the class of oriented planar graphs and prove that such a graph must have maximum degree at least 16; thus there exists an oriented planar graph with oriented chromatic number at least 17. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 175–190, 2007     

Contractibility techniques as a closure concept

We introduce a closure concept in the class of line graphs and claw‐free graphs based on contractibility of certain subgraphs in the line graph preimage. The closure can be considered as a common generalization and strengthening of the reduction techniques of Catlin and Veldman and of the closure concept introduced by the first author. We show that the closure is uniquely determined and the closure operation preserves the circumference of the graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 37–48, 2003     

Homomorphism–homogeneous graphs

We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–homogeneity. Further, we show that there are homomorphism–homogeneous graphs that do not contain the Rado graph as a spanning subgraph answering the second open question. We also treat the case of homomorphism–homogeneous graphs with loops allowed, showing that the corresponding decision problem is co–NP complete. Finally, we extend the list of considered morphism–types and show that the graphs for which monomorphisms can be extended to epimor‐phisms are complements of homomorphism–homogeneous graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 253–261, 2010     

Random graphons and a weak Positivstellensatz for graphs

In an earlier article, the authors proved that limits of convergent graph sequences can be described by various structures, including certain 2‐variable real functions called graphons, random graph models satisfying certain consistency conditions, and normalized, multiplicative and reflection positive graph parameters. In this article we show that each of these structures has a related, relaxed version, which are also equivalent. Using this, we describe a further structure equivalent to graph limits, namely probability measures on countable graphs that are ergodic with respect to the group of permutations of the nodes. As an application, we prove an analogue of the Positivstellensatz for graphs: we show that every linear inequality between subgraph densities that holds asymptotically for all graphs has a formal proof in the following sense: it can be approximated arbitrarily well by another valid inequality that is a “sum of squares” in the algebra of partially labeled graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory     

High‐girth cubic graphs are homomorphic to the Clebsch graph

We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5‐colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1 ). Hopkins and Staton [J Graph Theory 6(2) (1982), 115–121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477–504] proved that every (sub)cubic graph of girth at least 4 has an edge‐cut containing at least of the edges. The existence of such an edge‐cut follows immediately from the existence of a 5‐edge‐coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above‐described 5‐edge‐coloring; hence our theorem may also be viewed as a weak version of Ne?et?il's Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C₅). Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 241—259, 2011     

Intersections of graphs

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed image graph H. We introduce our techniques by proving that the lex graph has the largest number of homomorphisms into K₂ with one looped vertex (or equivalently, the largest number of independent sets) among graphs with fixed number of vertices and edges. Our main result is the solution to the extremal problem for the number of homomorphisms into P, the completely looped path of length 2 (known as the Widom–Rowlinson model in statistical physics). We show that there are extremal graphs that are threshold, give explicitly a list of five threshold graphs from which any threshold extremal graph must come, and show that each of these “potentially extremal” threshold graphs is in fact extremal for some number of edges. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 261–284, 2011     

On directed local chromatic number,shift graphs,and Borsuk‐like graphs

We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of “topologically t‐chromatic” graphs. We show that this minimum for large enough t‐chromatic Schrijver graphs and t‐chromatic generalized Mycielski graphs of appropriate parameters is ?t/4?+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 65‐82, 2010     

Planar graphs producing no strongly almost trivial embedding

We present here infinitely many planar graphs which have no strongly almost trivial embeddings. Then we conclude that “strongly almost trivial” is more strict concept than “almost trivial.”. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 319–326, 2003     

Cubic graphs with most automorphisms

We give a sharp bound for the order of the automorphism group of a connected simple cubic graph on a given number of vertices. For each number of vertices we construct a graph, unique in special cases, attaining the bound. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 99–115, 2010     

Cohomology of Oriented Tree Diagram Lie Algebras

Xu introduced a family of root-tree-diagram nilpotent Lie algebras of differential operators, in connection with evolution partial differential equations. We generalized his notion to more general oriented tree diagrams. These algebras are natural analogues of the maximal nilpotent Lie subalgebras of finite-dimensional simple Lie algebras. In this article, we use Hodge Laplacian to study the cohomology of these Lie algebras. The “total rank conjecture” and “b ₂-conjecture” for the algebras are proved. Moreover, we find the generating functions of the Betti numbers by means of Young tableaux for the Lie algebras associated with certain tree diagrams of single branch point. By these functions and Euler–Poincaré principle, we obtain analogues of the denominator identity for finite-dimensional simple Lie algebras. The result is a natural generalization of the Bott's classical result in the case of special linear Lie algebras.     

A planar hypohamiltonian graph with 48 vertices

We present a planar hypohamiltonian graph on 48 vertices, and derive some consequences. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 338–342, 2007     

Acyclic systems of representatives and acyclic colorings of digraphs

A natural digraph analog of the graph theoretic concept of “an independent set” is that of “an acyclic set of vertices,” namely a set not spanning a directed cycle. By this token, an analog of the notion of coloring of a graph is that of decomposition of a digraph into acyclic sets. We extend some known results on independent sets and colorings in graphs to acyclic sets and acyclic colorings of digraphs. In particular, we prove bounds on the topological connectivity of the complex of acyclic sets, and using them we prove sufficient conditions for the existence of acyclic systems of representatives of a system of sets of vertices. These bounds generalize a result of Tardos and Szabó. We prove a fractional version of a strong‐acyclic‐coloring conjecture for digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 177–189, 2008     

Forcing a Kr minor by high external connectivity

We investigate the minimal structure a graph H is required to have if H is to force a large complete minor in any graph in which it has high external connectivity. We observe that such graphs H must contain a large binary tree with some small additions, and prove that some canonical instances of this structure are also sufficient to force a large complete minor. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 241–264, 2002; DOI 10.1002/jgt.10026     

Strong Chromatic Index of 2‐Degenerate Graphs

We prove that the strong chromatic index of a 2‐degenerate graph is linear in the maximum degree Δ. This includes the class of all chordless graphs (graphs in which every cycle is induced) which in turn includes graphs where the cycle lengths are multiples of four, and settles a problem by Faudree et al. (Ars Combin 29(B) (1990), 205–211). © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 119–126, 2013     

Coloring the square of a planar graph

We prove that for any planar graph G with maximum degree Δ, it holds that the chromatic number of the square of G satisfies χ(G²) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 110–124, 2003     

Numbers of edges in supermagic graphs

A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we establish some bounds for the number of edges in supermagic graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 52: 15–26, 2006     

Short proofs for two theorems of Chien,Hell and Zhu

In (J Graph Theory 33 (2000), 14–24), Hell and Zhu proved that if a series–parallel graph G has girth at least 2?(3k?1)/2?, then χ_c(G)≤4k/(2k?1). In (J Graph Theory 33 (2000), 185–198), Chien and Zhu proved that the girth condition given in (J Graph Theory 33 (2000), 14–24) is sharp. Short proofs of both results are given in this note. © 2010 Wiley Periodicals, Inc. J Graph 66: 83‐88, 2010 Theory