On permutation labeling

We determine all permutation graphs of order ?9. We prove that every bipartite graph of order ?50 is a permutation graph. We convert the conjecture stating that “every tree is a permutation graph” to be “every bipartite graph is a permutation graph”.     

The chromatic number of oriented graphs

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with bounded degree. We show that there exist oriented k-trees with chromatic number at least 2^k+1 - 1 and that every oriented k-tree has chromatic number at most (k + 1) × 2^k. For 2-trees and 3-trees we decrease these upper bounds respectively to 7 and 16 and show that these new bounds are tight. As a particular case, we obtain that oriented outerplanar graphs have chromatic number at most 7 and that this bound is tight too. We then show that every oriented graph with maximum degree k has chromatic number at most (2k - 1) × 2^2k-2. For oriented graphs with maximum degree 2 we decrease this bound to 5 and show that this new bound is tight. For oriented graphs with maximum degree 3 we decrease this bound to 16 and conjecture that there exists no such connected graph with chromatic number greater than 7. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 191–205, 1997     

On the edge-connectivity of graphs with two orbits of the same size

It is well known that the edge-connectivity of a simple, connected, vertex-transitive graph attains its regular degree. It is then natural to consider the relationship between the graph’s edge-connectivity and the number of orbits of its automorphism group. In this paper, we discuss the edge connectedness of graphs with two orbits of the same size, and characterize when these double-orbit graphs are maximally edge connected and super-edge-connected. We also obtain a sufficient condition for some double-orbit graphs to be λ^′-optimal. Furthermore, by applying our results we obtain some results on vertex/edge-transitive bipartite graphs, mixed Cayley graphs and half vertex-transitive graphs.     

Matching theory and Barnette's conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

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     

Ring graphs and complete intersection toric ideals

We study the family of graphs whose number of primitive cycles equals its cycle rank. It is shown that this family is precisely the family of ring graphs. Then we study the complete intersection property of toric ideals of bipartite graphs and oriented graphs. An interesting application is that complete intersection toric ideals of bipartite graphs correspond to ring graphs and that these ideals are minimally generated by Gröbner bases. We prove that any graph can be oriented such that its toric ideal is a complete intersection with a universal Gröbner basis determined by the cycles. It turns out that bipartite ring graphs are exactly the bipartite graphs that have complete intersection toric ideals for any orientation.     

A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs

Acyclic directed graphs are widely used in many fields of economic and social sciences. This has generated considerable interest in algorithms for drawing “good” maps of acyclic diagraphs. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of crossing arcs. In this paper, we present a branch and bound algorithm for solving the problem of minimizing the number of crossing arcs in a bipartite graph. Computational results are reported on a set of randomly generated test problems.     

The graph formulation of the union-closed sets conjecture

The union-closed sets conjecture asserts that in a finite non-trivial union-closed family of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs. We derive that the union-closed sets conjecture holds for all union-closed families being the union-closure of sets of size at most three.     

Obstructions for acyclic local tournament orientation completions

The orientation completion problem for a fixed class of oriented graphs asks whether a given partially oriented graph can be completed to an oriented graph in the class. Orientation completion problems have been studied recently for several classes of oriented graphs, including local tournaments. Local tournaments are intimately related to proper circular-arc graphs and proper interval graphs. In particular, proper interval graphs are precisely those which can be oriented as acyclic local tournaments. In this paper we determine all obstructions for acyclic local tournament orientation completions. These are in a sense minimal partially oriented graphs that cannot be completed to acyclic local tournaments. Our results imply that a polynomial time certifying algorithm exists for the acyclic local tournament orientation completion problem.     

Excluded checkerboard colourable ribbon graph minors

Motivated by the Eulerian ribbon graph minors, in this paper we introduce the notion of checkerboard colourable minors for ribbon graphs and its dual: bipartite minors for ribbon graphs. Motivated by the bipartite minors of abstract graphs, another bipartite minors for ribbon graphs, i.e. the bipartite ribbon graph join minors are also introduced. Using these minors then we give excluded minor characterizations of the classes of checkerboard colourable ribbon graphs, bipartite ribbon graphs, plane checkerboard colourable ribbon graphs and plane bipartite ribbon graphs.     

Zero forcing sets and bipartite circulants

In this paper we introduce a class of regular bipartite graphs whose biadjacency matrices are circulant matrices – a generalization of circulant graphs which happen to be bipartite – and we describe some of their properties. Notably, we compute upper and lower bounds for the zero forcing number for such a graph based only on the parameters that describe its biadjacency matrix. The main results of the paper characterize the bipartite circulant graphs that achieve equality in the lower bound and compute their minimum ranks.     

图论中若干基本概念的历史注记

考察了图与子图,树,匹配,欧拉图与哈密尔顿图,可平面图,以及与图的连通性和图的着色有关的若干图论基本概念的历史背景.     

定向图的斜秩

定向图Gσ是一个不含有环(loop)和重边的有向图,其中G称作它的基图.S(Gσ)是Gσ的斜邻接矩阵.S(Gσ)的秩称为Gσ的斜秩,记为sr(Gσ).定向图的斜邻接矩阵是斜对称的,因而,它的斜秩是偶数.本文主要考虑简单定向图的斜秩,首先给出斜秩的一些简单基本知识,紧接着分别刻画斜秩是2的定向图和斜秩是4的带有悬挂点的定向图;其次利用匹配数给出具有n个顶点、围长是k的单圈图的斜秩表达式;作为推论,列出斜秩是4的所有单圈图和带有悬挂点的双圈图;另外研究具有n个顶点、围长是k的单圈图的图类中斜秩的最小值,并刻画了极图;最后研究斜邻接矩阵是非奇异的定向单圈图.     

Minimally non-Pfaffian graphs

We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K_3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion.We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs.     

Graham’s pebbling conjecture on product of complete bipartite graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs G and H, f( G x H) ⩽ f( G) f( H). We show that Graham’s conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are complete bipartite graphs.     

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     

Nowhere‐Zero Flows on Signed Complete and Complete Bipartite Graphs

Bouchet's conjecture asserts that each signed graph which admits a nowhere‐zero flow has a nowhere‐zero 6‐flow. We verify this conjecture for two basic classes of signed graphs—signed complete and signed complete bipartite graphs by proving that each such flow‐admissible graph admits a nowhere‐zero 4‐flow and we characterise those which have a nowhere‐zero 2‐flow and a nowhere‐zero 3‐flow.     

Bipartite density of cubic graphs

We first obtain the exact value for bipartite density of a cubic line graph on n vertices. Then we give an upper bound for the bipartite density of cubic graphs in terms of the smallest eigenvalue of the adjacency matrix. In addition, we characterize, except in the case n=20, those graphs for which the upper bound is obtained.     

A note on the smallest connected non-traceable cubic bipartite planar graph

A graph is traceable if it contains a Hamiltonian path. We present a connected non-traceable cubic bipartite planar graph with 52 vertices and prove that there are no smaller such graphs.