The height of a 4-cycle in triangle-free 1-planar graphs with minimum degree 5

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. It is known that each 1-planar graph has a vertex of degree at most 7, and also either a vertex of degree at most 4 or a cycle of length at most 4. In the article, it is proven that each triangle-free 1-planar graph of degree less than 5 has a 4-cycle that consists of vertices of degree at most 8.     

Joins of 1-planar graphs

A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once.In this paper,we study 1-planar graph joins.We prove that the join G + H is 1-planar if and only if the pair [G,H] is subgraph-majorized by one of pairs [C3 ∪ C3,C3],[C4,C4],[C4,C3],[K2,1,1,P3] in the case when both elements of the graph join have at least three vertices.If one element has at most two vertices,then we give several necessary/sufficient conditions for the bigger element.     

Minimal non-1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G-e is 1-planar for every edge e of G. We prove that there are infinitely many minimal non-1-planar graphs (MN-graphs). It is known that every 6-vertex graph is 1-planar. We show that the graph K₇-K₃ is the unique 7-vertex MN-graph.     

Equitable Coloring of Three Classes of 1-planar Graphs

A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree Δ at least 15, 13 or 12 has an equitable Δ-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.     

1-平面图的结构性质及其在无圈边染色上的应用

一个图称为是1-平面的如果它可以画在一个平面上使得它的每条边最多交叉另外一条边.本文描述了任意1-平面图中小于等于7度点之邻域的局部结构,解决了由Fabrici和Madaras提出的两个关于1-平面图图类中轻图存在性的问题,证明了每个最大度是△的1-平面图G是无圈列表max{2△-2,△+83}-边可选的.     

A Totally(Δ+1)-colorable 1-planar Graph with Girth at Least Five

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge.In this paper,we prove that every 1-planar graph G with maximum degree Δ(G)≥12 and girth at least five is totally(Δ(G)+1)-colorable.     

The structure of 1-planar graphs

A graph is called 1-planar if it can be drawn in the plane so that each its edge is crossed by at most one other edge. In the paper, we study the existence of subgraphs of bounded degrees in 1-planar graphs. It is shown that each 1-planar graph contains a vertex of degree at most 7; we also prove that each 3-connected 1-planar graph contains an edge with both endvertices of degrees at most 20, and we present similar results concerning bigger structures in 1-planar graphs with additional constraints.     

List edge and list total coloring of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree Δ is (Δ+1)-edge-choosable and (Δ+2)- total-choosable if Δ≥16, and is Δ-edge-choosable and (Δ+1)-total-choosable if Δ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.     

1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.     

Minimal 2-matching-covered graphs

A perfect 2-matching M of a graph G is a spanning subgraph of G such that each component of M is either an edge or a cycle. A graph G is said to be 2-matching-covered if every edge of G lies in some perfect 2-matching of G. A 2-matching-covered graph is equivalent to a “regularizable” graph, which was introduced and studied by Berge. A Tutte-type characterization for 2-matching-covered graph was given by Berge. A 2-matching-covered graph is minimal if G−e is not 2-matching-covered for all edges e of G. We use Berge’s theorem to prove that the minimum degree of a minimal 2-matching-covered graph other than K₂ and K₄ is 2 and to prove that a minimal 2-matching-covered graph other than K₄ cannot contain a complete subgraph with at least 4 vertices.     

On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

Long cycles and spanning subgraphs of locally maximal 1-planar graphs

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is Hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many nontraceable 5-connected 1-planar graphs are presented.     

On the Connectivity of Visibility Graphs

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesník (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71?C93, 1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesník by showing that for any two vertices v and w in a graph of diameter 2, if deg(v)??deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most ? collinear vertices has connectivity at least $\frac{n-1}{\ell-1}$ , which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that ?=4 we improve this bound to two thirds of the minimum degree.     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

On intersections of interval graphs

If one can associate with each vertex of a graph an interval of a line, so that two intervals intersect just when the corresponding vertices are joined by an edge, then one speaks of an interval graph.It is shown that any graph on v vertices is the intersection (“product”) of at most [$\text{1}\text{2}$v] interval graphs on the same vertex set.For v=2k, k factors are necessary for, and only for, the complete k-partite graph K_2,2,…,2.Some results for the hypergraph generalization of this question are also obtained.     

On (<Emphasis Type="Italic">p</Emphasis>, 1)-total labelling of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ(G) ≥ 8p+4 or Δ(G) ≥ 6p+2 and g(G) ≥ 4. As a consequence, the well-known (p, 1)-total labelling conjecture has been confirmed for some 1-planar graphs.     

Total weight choosability of graphs

A graph G = (V, E) is called (k, k′)‐total weight choosable if the following holds: For any total list assignment L which assigns to each vertex x a set L(x) of k real numbers, and assigns to each edge e a set L(e) of k′ real numbers, there is a mapping f: V∪E→? such that f(y)∈L(y) for any y∈V∪Eand for any two adjacent vertices x, x′, . We conjecture that every graph is (2, 2)‐total weight choosable and every graph without isolated edges is (1, 3)‐total weight choosable. It follows from results in [7] that complete graphs, complete bipartite graphs, trees other than K₂ are (1, 3)‐total weight choosable. Also a graph G obtained from an arbitrary graph H by subdividing each edge with at least three vertices is (1, 3)‐total weight choosable. This article proves that complete graphs, trees, generalized theta graphs are (2, 2)‐total weight choosable. We also prove that for any graph H, a graph G obtained from H by subdividing each edge with at least two vertices is (2, 2)‐total weight choosable as well as (1, 3)‐total weight choosable. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:198‐212, 2011     

On total colorings of some special 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we verify the total coloring conjecture for every 1-planar graph G if either Δ(G) ≥ 9 and g(G) ≥ 4, or Δ(G) ≥ 7 and g(G) ≥ 5, where Δ(G) is the maximum degree of G and g(G) is the girth of G.     

Construction of a family of graphs with a small induced proper subgraph with minimum degree 3

We investigate the following question proposed by Erd?s: Is there a constant c such that, for each n, if G is a graph with n vertices, 2n-1edges, andδ(G)?3, then G contains an induced proper subgraph H with at least cn vertices andδ(H)?3?Previously we showed that there exists no such constant c by constructing a family of graphs whose induced proper subgraph with minimum degree 3 contains at most vertices. In this paper we present a construction of a family of graphs whose largest induced proper subgraph with minimum degree 3 is K₄. Also a similar construction of a graph with n vertices and αn+β edges is given.     

List Edge Coloring of Outer-1-planar Graphs

Acta Mathematicae Applicatae Sinica, English Series - A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once. It...