On Group Choosability of Total Graphs

In this paper, we study the group and list group colorings of total graphs and present group coloring versions of the total and list total colorings conjectures. We establish the group coloring version of the total coloring conjecture for the following classes of graphs: graphs with small maximum degree, two-degenerate graphs, planner graphs with maximum degree at least 11, planner graphs without certain small cycles, outerplanar graphs and near outerplanar graphs with maximum degree at least 4. In addition, the group version of the list total coloring conjecture is established for forests, outerplanar graphs and graphs with maximum degree at most two.     

Enumeration of labeled outerplanar bicyclic and tricyclic graphs

The class of outerplanar graphs is used for testing the average complexity of algorithms on graphs. A random labeled outerplanar graph can be generated by a polynomial algorithm based on the results of an enumeration of such graphs. By a bicyclic (tricyclic) graph we mean a connected graph with cyclomatic number 2 (respectively, 3). We find explicit formulas for the number of labeled connected outerplanar bicyclic and tricyclic graphs with n vertices and also obtain asymptotics for the number of these graphs for large n. Moreover, we obtain explicit formulas for the number of labeled outerplanar bicyclic and tricyclic n-vertex blocks and deduce the corresponding asymptotics for large n.     

Computation of the center and diameter of outerplanar graphs

The center of a graph is the set of vertices with minimum eccentricity. An outerplanar graph is a planar segmentation of a polygon. We define a notion of edge eccentricities for the edges of an outerplanar graph. We present an algorithm which efficiently computes these edge eccentricities. Knowledge of the edge eccentricities allows subsequent linear time computation of the center and diameter of outerplanar graphs. The computation of edge eccentricities is shown to require linear time for certain subclasses of outerplanar graphs.     

Thickness-Two Graphs Part Two: More New Nine-Critical Graphs,Independence Ratio,Cloned Planar Graphs,and Singly and Doubly Outerplanar Graphs

There are numerous means for measuring the closeness to planarity of a graph such as crossing number, splitting number, and a variety of thickness parameters. We focus on the classical concept of the thickness of a graph, and we add to earlier work in [4]. In particular, we offer new 9-critical thickness-two graphs on 17, 25, and 33 vertices, all of which provide counterexamples to a conjecture on independence ratio of Albertson; we investigate three classes of graphs, namely singly and doubly outerplanar graphs, and cloned planar graphs. We give a sharp upper bound for the largest chromatic number of the cloned planar graphs, and we give upper and lower bounds for the largest chromatic number of the former two classes.     

Minimum rank of outerplanar graphs

The problem of finding the minimum rank over all symmetric matrices corresponding to a given graph has grown in interest recently. It is well known that the minimum rank of any graph is bounded above by the clique cover number, the minimum number of cliques needed to cover all edges of the graph. We generalize the idea of the clique cover number by defining the rank sum of a cover to be the sum of the minimum ranks of the graphs in the cover. Using this idea we obtain a combinatorial solution to the minimum rank problem for an outerplanar graph. As a consequence the minimum rank of an outerplanar graph is field independent and all outerplanar graphs have a universally optimal matrix. We also consider implications of the main result to the inverse inertia problem.     

Star Edge Coloring of Some Classes of Graphs

A star edge coloring of a graph is a proper edge coloring without bichromatic paths and cycles of length four. In this article, we establish tight upper bounds for trees and subcubic outerplanar graphs, and derive an upper bound for outerplanar graphs.     

Invalid proofs on incidence coloring

Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ=4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ≥7 is Δ+1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ+1)-incidence colorable.     

Asymmetric directed graph coloring games

This note generalizes the (a,b)-coloring game and the (a,b)-marking game which were introduced by Kierstead [H.A. Kierstead, Asymmetric graph coloring games, J. Graph Theory 48 (2005) 169-185] for undirected graphs to directed graphs. We prove that the (a,b)-chromatic and (a,b)-coloring number for the class of orientations of forests is b+2 if b≤a, and infinity otherwise. From these results we deduce upper bounds for the (a,b)-coloring number of oriented outerplanar graphs and of orientations of graphs embeddable in a surface with bounded girth.     

Homomorphisms of 2-edge-colored graphs

In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.     

Homomorphisms of 2-edge-colored graphs

In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.     

On properties of random dissections and triangulations

In this work we study properties of random graphs that are drawn uniformly at random from the class consisting of biconnected outerplanar graphs, or equivalently dissections of large convex polygons. We obtain very sharp concentration results for the number of vertices of any given degree, and for the number of induced copies of a given fixed graph. Our method gives similar results for random graphs from the class of triangulations of convex polygons.     

Algebraic characterizations of outerplanar and planar graphs

A drawing of a graph in the plane is even if nonadjacent edges have an even number of intersections. Hanani’s theorem characterizes planar graphs as those graphs that have an even drawing. In this paper we present an algebraic characterization of graphs that have an even drawing. Together with Hanani’s theorem this yields an algebraic characterization of planar graphs. We will also present algebraic characterizations of subgraphs of paths, and of outerplanar graphs.     

Excluded-Minor Characterization of Apex-Outerplanar Graphs

The class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: \(K_4\) and \(K_{2,3}\). The class of graphs that contain a vertex whose removal leaves an outerplanar graph is also minor-closed. We provide the complete list of 57 excluded minors for this class.     

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.     

Generalized outerplanar index of a graph

We define the generalized outerplanar index of a graph and give a full characterization of graphs with respect to this index.     

Acrylic improper colorings of graphs

In this article, we introduce the new notion of acyclic improper colorings of graphs. An improper coloring of a graph is a vertex-coloring in which adjacent vertices are allowed to have the same color, but each color class V_i satisfies some condition depending on i. Such a coloring is acyclic if there are no alternating 2-colored cycles. We prove that every outerplanar graph can be acyclically 2-colored in such a way that each monochromatic subgraph has degree at most five and that this result is best possible. For planar graphs, we prove some negative results and state some open problems. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 97–107, 1999     

Approximation of pathwidth of outerplanar graphs

There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph G, finds a path decomposition of G of pathwidth at most twice the pathwidth of G plus one. To obtain the result, several relations between the pathwidth of a biconnected outerplanar graph and its dual are established.     

Thickness and outerthickness for embedded graphs

We prove new upper bounds for the thickness and outerthickness of a graph in terms of its orientable and nonorientable genus by applying the method of deleting spanning disks of embeddings to approximate the thickness and outerthickness. We also show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This implies that the outerthickness of the torus (the maximum outerthickness of all toroidal graphs) is 3. Finally, we show that all graphs embeddable in the double torus have thickness at most 3 and outerthickness at most 5.     

Geometry of large Boltzmann outerplanar maps

We study the phase diagram of random outerplanar maps sampled according to nonnegative Boltzmann weights that are assigned to each face of a map. We prove that for certain choices of weights the map looks like a rescaled version of its boundary when its number of vertices tends to infinity. The Boltzmann outerplanar maps are then shown to converge in the Gromov‐Hausdorff sense towards the α‐stable looptree introduced by Curien and Kortchemski (2014), with the parameter α depending on the specific weight‐sequence. This allows us to describe the transition of the asymptotic geometric shape from a deterministic circle to the Brownian tree.     

外平面图的有界染色

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图 G的k-有界染色数Xk(G)是指对G进行k-有界染色用的最少颜色数．本文给出了n个顶点的外平面图能用[n/k]种颜色k-有界染色的一些充分条件．