The intersection dimension of a graph with respect to a class of graphs is the minimum such that is the intersection of some graphs on the vertex set belonging to . In this paper we follow [ Kratochv’ıl J., Tuza Z.: Intersection dimensions of graph classes, Graphs and Combinatorics 10 (1994), 159–168 ] and show that for some pairs of graph classes , the intersection dimension of graphs from with respect to is unbounded.
Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an embedding G into its complement [G̅]. In this note, we consider a problem concerning the uniqueness of such an embedding.
Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.
In this note we give a simple proof of a result of Richter and Siran by basic counting method, which says that the crossing number of in a surface with Euler genus ε is ⎣n/(2ε+2)⎦ n - (ε+1)(1+⎣n/(2ε+2)⎦).
A proper vertex coloring of a graph is acyclic if there is no bicolored cycle in . In other words, each cycle of must be colored with at least three colors. Given a list assignment , if there exists an acyclic coloring of such that for all , then we say that is acyclically -colorable. If is acyclically -colorable for any list assignment with for all , then is acyclically -choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without 4-cycles...
A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours such that adjacent vertices receive distinct colours. Such a k-colouring is called acyclic, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, every cycle in G has at least three distinct colours. Acyclic colourings were introduced by Gr¨unbaum in 1973, and since then have...
Within geometric topology of 3-manifolds (with or without boundary), a representation theory exists, which makes use of 4-coloured graphs. Aim of this paper is to translate the homeomorphism problem for the represented manifolds into an equivalence problem for 4-coloured graphs, by means of a finite number of graph-moves, called dipole moves. Moreover, interesting consequences are obtained, which are related with the same problem in the n-dimensional setting.