Maximal planar graphs of diameter two

A maximal planar graph is a simple planar graph in which every face is a triangle. We show here that such graphs with maximum degree Δ and diameter two have no more than 3/2Δ + 1 vertices. We also show that there exist maximal planar graphs with diameter two and exactly [3/2Δ + 1] vertices.     

Maximum Order of Triangle‐Free Graphs with a Given Rank

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle‐free graphs with a given rank and characterize all such graphs achieving the maximum order.     

Drawing planar 3-trees with given face areas

We study straight-line drawings of planar graphs such that each interior face has a prescribed area. It was known that such drawings exist for all planar graphs with maximum degree 3. We show here that such drawings exist for all planar partial 3-trees, i.e., subgraphs of a triangulated planar graph obtained by repeatedly inserting a vertex in one triangle and connecting it to all vertices of the triangle. Moreover, vertices have rational coordinates if the face areas are rational, and we can bound the resolution. We also give some negative results for other graph classes.     

On Triangle‐Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph

We prove a decomposition theorem for the class of triangle‐free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove that every graph of girth at least five in this class is 3‐colorable.     

On the structure of clique‐free graphs

Using a clever inductive counting argument Erd?s, Kleitman and Rothschild showed in 1976 that almost all triangle‐free graphs are bipartite, i.e., that the cardinality of the two graph classes is asymptotically equal. In this paper we investigate the structure of the “few” triangle‐free graphs which are not bipartite. As it turns out, with high probability, these graphs are bipartite up to a few vertices. More precisely, almost all of them can be made bipartite by removing just one vertex. Almost all others can be made bipartite by removing two vertices, and then three vertices and so on. We also show that similar results hold if we replace “triangle‐free” by K_??+1‐free and “bipartite” by ??‐partite. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 37–53, 2001     

Planar Hypohamiltonian Graphs on 40 Vertices

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer‐aided generation of certain families of planar graphs with girth 4 and a fixed number of 4‐faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.     

Decompositions of highly connected graphs into paths of length 3

We prove that a 171‐edge‐connected graph has an edge‐decomposition into paths of length 3 if and only its size is divisible by 3. It is a long‐standing problem whether 2‐edge‐connectedness is sufficient for planar triangle‐free graphs, and whether 3‐edge‐connectedness suffices for graphs in general. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 286–292, 2008     

Recognizing bull-free perfect graphs

A bull is the graph obtained from a triangle by adding two pendant vertices adjacent to distinct vertices of the triangle. Chvátal and Sbihi showed that the strong perfect graph conjecture holds for Bull-free graphs. We give a polynomial time recognition algorithm for Bull-free perfect graphs.     

Embeddings of chemical graphs in hypercubes

We study planar graphs embedded in the plane that have chemical applications: the degrees of all vertices are 3 or 2, all internal faces but one or two arer-gons, and each internal face is a simply connected domain. For wide classes of such graphs, we solve the existence problem for embeddings of the graph metric on the vertices in multidimensional cubes or cubical lattices preserving or doubling all the distances. Incidentally we present a complete classification of some interesting families of such graphs. Translated fromMatematicheskie Zametki, Vol. 68, No. 3, pp. 339–352, September, 2000.     

Achromatic number of fragmentable graphs

A complete coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at least one edge. The achromatic number ψ(G) is the greatest number of colors in such a coloring. We say a class of graphs is fragmentable if for any positive ε, there is a constant C such that any graph in the class can be broken into pieces of size at most C by removing a proportion at most ε of the vertices. Examples include planar graphs and grids of fixed dimension. Determining the achromatic number of a graph is NP‐complete in general, even for trees, and the achromatic number is known precisely for only very restricted classes of graphs. We extend these classes very considerably, by giving, for graphs in any class which is fragmentable, triangle‐free, and of bounded degree, a necessary and sufficient condition for a sufficiently large graph to have a complete coloring with a given number of colors. For the same classes, this gives a tight lower bound for the achromatic number of sufficiently large graphs, and shows that the achromatic number can be determined in polynomial time. As examples, we give exact values of the achromatic number for several graph families. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:94–114, 2010     

Tiled partial cubes

In the quest to better understand the connection between median graphs, triangle‐free graphs and partial cubes, a hierarchy of subclasses of partial cubes has been introduced. In this article, we study the role of tiled partial cubes in this scheme. For instance, we prove that almost‐median graphs are tiled and that tiled partial cubes are semi‐median. We also describe median graphs as tiled partial cubes without convex Q and extend an inequality for median graphs to a larger subclass of partial cubes. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 91–103, 2002     

Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number

Asteroidal Triple‐free (AT‐free) graphs have received considerable attention due to their inclusion of various important graphs families, such as interval and cocomparability graphs. The asteroidal number of a graph is the size of a largest subset of vertices such that the removal of the closed neighborhood of any vertex in the set leaves the remaining vertices of the set in the same connected component. (AT‐free graphs have asteroidal number at most 2.) In this article, we characterize graphs of bounded asteroidal number by means of a vertex elimination ordering, thereby solving a long‐standing open question in algorithmic graph theory. Similar characterizations are known for chordal, interval, and cocomparability graphs.     

Planar graphs without 4‐cycles adjacent to 3‐cycles are list vertex 2‐arborable

It is known that not all planar graphs are 4‐choosable; neither all of them are vertex 2‐arborable. However, planar graphs without 4‐cycles and even those without 4‐cycles adjacent to 3‐cycles are known to be 4‐choosable. We extend this last result in terms of covering the vertices of a graph by induced subgraphs of variable degeneracy. In particular, we prove that every planar graph without 4‐cycles adjacent to 3‐cycles can be covered by two induced forests. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 234–240, 2009     

Further extensions of the Grötzsch Theorem

The Grötzsch Theorem states that every triangle-free planar graph admits a proper 3-coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving 3-colorability of planar graphs with at most three triangles, is perhaps the most known. A lot of attention was also given to extending 3-colorings of subgraphs to the whole graph. In this paper, we consider 3-colorings of planar graphs with at most one triangle. Particularly, we show that precoloring of any two non-adjacent vertices and precoloring of a face of length at most 4 can be extended to a 3-coloring of the graph. Additionally, we show that for every vertex of degree at most 3, a precoloring of its neighborhood with the same color extends to a 3-coloring of the graph. The latter result implies an affirmative answer to a conjecture on adynamic coloring. All the presented results are tight.     

Infinite paths in planar graphs IV,dividing cycles

Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if, and only if, the deletion of any finite set of vertices results in at most two infinite components. In this article, we prove this conjecture for graphs with no dividing cycles and for graphs with infinitely many vertex disjoint dividing cycles. A cycle in an infinite plane graph is called dividing if both regions of the plane bounded by this cycle contain infinitely many vertices of the graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 173–195, 2006     

On the max‐cut problem for a planar,cubic, triangle‐free graph,and the Chinese postman problem for a planar triangulation

Every 3‐connected planar, cubic, triangle‐free graph with n vertices has a bipartite subgraph with at least 29n/24 ? 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Examples show that the constant 29/24 = 1.2083… cannot be raised to more than 47/38 = 1.2368…. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 261–269, 2006     

Infinite paths in planar graphs II,structures and ladder nets

A graph is k‐indivisible, where k is a positive integer, if the deletion of any finite set of vertices results in at most k – 1 infinite components. In 1971, Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if and only if it is 3‐indivisible. In this paper, we prove a structural result for 2‐indivisible infinite planar graphs. This structural result is then used to prove Nash‐Williams conjecture for all 4‐connected 2‐indivisible infinite planar graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 247–266, 2005     

On 3-regular 4-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian), if for any sequence of k distinct vertices v₁,…,v_kof G there exists a cycle (respectively, hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability and posed the question of the existence of 3-regular 4-ordered (hamiltonian) graphs other than K₄ and K_3,3. Ng and Schultz observed that a 3-regular 4-ordered graph on more than 4 vertices is triangle free. We prove that a 3-regular 4-ordered graph G on more than 6 vertices is square free,and we show that the smallest graph that is triangle and square free, namely the Petersen graph, is 4-ordered. Furthermore, we prove that the smallest graph after K₄ and K_3,3 that is 3-regular 4-ordered hamiltonianis the Heawood graph. Finally, we construct an infinite family of 3-regular 4-ordered graphs.     

Projective‐Planar Graphs with no K3, 4‐Minor. II

The authors previously published an iterative process to generate a class of projective‐planar K_{3, 4}‐free graphs called “patch graphs.” They also showed that any simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K_{3, 4}‐free is a subgraph of a patch graph. In this article, we describe a simpler and more natural class of cubic K_{3, 4}‐free projective‐planar graphs that we call Möbius hyperladders. Furthermore, every simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K_{3, 4}‐free is a minor of a Möbius hyperladder. As applications of these structures we determine the page number of patch graphs and of Möbius hyperladders.     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.