Cubic graphs with crossing number two

It is proved that every cubic graph with crossing number at least two contains a subdivision of one of eight graphs.     

Graph minors and the crossing number of graphs

There are three general lower bound techniques for the crossing numbers of graphs, all of which can be traced back to Leighton's work on applications of crossing number in VLSI: the Crossing Lemma, the Bisection Method, and the Embedding Method. In this contribution, we sketch their adaptations to the minor crossing number.     

Additivity of the crossing number of graphs with connectivity 2

We prove that the crossing number of graphs with connectivity 2 has in certain cases an additive property analogous to that of crossing number of graphs with connectivity ≤1.     

Forbidden subgraphs for graphs with line graphs of crossing number ≤1

The purpose of this paper is to give a characterization of graphs with line graphs of crossing number at most 1 in term of forbidden subgraphs.     

Infinite families of crossing-critical graphs with a given crossing number

A graph is crossing-critical if deleting any edge decreases its crossing number on the plane. It is proved that, for any n ? 3, there is an infinite family of 3-connected crossing-critical graphs with crossing number n.     

Vertex pancyclic graphs

Let G be a graph of order n. A graph G is called pancyclic if it contains a cycle of length k for every 3kn, and it is called vertex pancyclic if every vertex is contained in a cycle of length k for every 3kn. In this paper, we shall present different sufficient conditions for graphs to be vertex pancyclic.     

On 3-regular graphs having crossing number at least 2

We give a planar proof of the fact that if G is a 3-regular graph minimal with respect to having crossing number at least 2, then the crossing number of G is 2.     

Vertex partitions of chordal graphs

A k‐tree is a chordal graph with no (k + 2)‐clique. An ?‐tree‐partition of a graph G is a vertex partition of G into ‘bags,’ such that contracting each bag to a single vertex gives an ?‐tree (after deleting loops and replacing parallel edges by a single edge). We prove that for all k ≥ ? ≥ 0, every k‐tree has an ?‐tree‐partition in which each bag induces a connected ‐tree. An analogous result is proved for oriented k‐trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 167–172, 2006     

Vertex degrees of planar graphs

Let G be a planar graph having n vertices with vertex degrees d₁, d₂,…,d_n. It is shown that $\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{d}{}_{\mathrm{i}}{}^2\text{≤ 2n}{}^2\text{+ O(n)}$. The main term in this upper bound is best possible.     

Vertex partitions of r-edge-colored graphs

Let G be an edge-colored graph.The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G.In the authors' previous work,it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P=NP.In this paper the authors show that for any fixed integer r≥5,if the edges of a graph G are colored by r colors,called an r-edge-colored graph,the problem remains NP-complete.Similar result holds for the monochromatic path(cycle)partition problem.Therefore,to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting. A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.     

Subdivisions in apex graphs

The Kelmans-Seymour conjecture states that every 5-connected nonplanar graph contains a subdivided K ₅. Certain questions of Mader propose a “plan” towards a possible resolution of this conjecture. One part of this plan is to show that every 5-connected nonplanar graph containing K^-₄K^{-}_{4} or K _2,3 as a subgraph has a subdivided K ₅. Recently, Ma and Yu showed that every 5-connected nonplanar graph containing K^-₄K^{-}_{4} as a subgraph has a subdivided K ₅. We take interest in K _2,3 and prove that every 5-connected nonplanar apex graph containing K _2,3 as a subgraph contains a subdivided K ₅. The result of Ma and Yu can be used in a short discharging argument to prove that every 5-connected nonplanar apex graph contains a subdivided K ₅; here we propose a longer proof whose merit is that it avoids the use of discharging and employs a more structural approach; consequently it is more amenable to generalization.     

Vertex pancyclicity in quasi-claw-free graphs

A graph G is called quasi-claw-free if for any two vertices x and y with distance two there exists a vertex u∈N(x)∩N(y) such that N[u]⊆N[x]∪N[y]. This concept is a natural extension of the classical claw-free graphs. In this paper, we present two sufficient conditions for vertex pancyclicity in quasi-claw-free graphs, namely, quasilocally connected and almost locally connected graphs. Our results include some well-known results on claw-free graphs as special cases. We also give an affirmative answer to a problem proposed by Ainouche.     

Vertex reconstruction in Cayley graphs

In this survey paper we review recent results on the vertex reconstruction problem (which is not related to Ulam’s problem) in Cayley graphs. The problem of reconstructing an arbitrary vertex x from its r-neighbors, that are, vertices at distance at most r from x, consists of finding the minimum restrictions on the number of r-neighbors when such a reconstruction is possible. We discuss general results for simple, regular and Cayley graphs. To solve this problem for given Cayley graphs, it is essential to investigate their structural and combinatorial properties. We present such properties for Cayley graphs on the symmetric group and the hyperoctahedral group (the group of signed permutations) and overview the main results for them. The choice of generating sets for these graphs is motivated by applications in coding theory, computer science, molecular biology and physics.     

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.     

Vertex partitions of non-complete graphs into connected monochromatic k-regular graphs

In a landmark paper, Erd?s et al. (1991) [3] proved that if $G$ is a complete graph whose edges are colored with $r$ colors then the vertex set of $G$ can be partitioned into at most $c{r}^{2}logr$ monochromatic, vertex disjoint cycles for some constant $c$. Sárközy extended this result to non-complete graphs, and Sárközy and Selkow extended it to $k$-regular subgraphs. Generalizing these two results, we show that if $G$ is a graph with independence number $\alpha \left(G\right)=\alpha$ whose edges are colored with $r$ colors then the vertex set of $G$ can be partitioned into at most ${\left(\alpha r\right)}^{c(\alpha rlog\left(\alpha r\right)+k)}$ vertex disjoint connected monochromatic$k$-regular subgraphs of $G$ for some constant $c$.     

Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].