A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. in [9] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs.

We prove the structural result on normal plane maps, which applies to the vertex distance colouring of plane maps. The vertex distance-t chromatic number of a plane graph G with maximum degree Δ(G) ≤ D, D ≥ 12 is proved to be upper bounded by $6+[(2D+12)/(D-2)]({(D-1)}^{(t-1)}-1)$. This improves a recent bound $6+[(3D+3)/(D-2)]({(D-1)}^{t-1}-1)$, D ≥ 8 by Jendrol’ and Skupień, and the upper bound for distance-2 chromatic number.

The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp. The purpose of this paper is to improve this 21 to 20, which is best possible.

A twin edge k-coloring of a graph G is a proper edge coloring of G with the elements of Zk so that the induced vertex coloring in which the color of a vertex v in G is the sum (in Zk) of the colors of the edges incident with v is a proper vertex coloring. The minimum k for which G has a twin edge k-coloring is called the twin chromatic index of G. Among the results presented are formulas for the twin chromatic index of each complete graph and each complete bipartite graph

We introduce object systems as a common generalization of graphs, hypergraphs, digraphs and relational structures. Let C be a concrete category, a simple object system over C is an ordered pair S = (V,E), where E = A₁,A₂,...,Aₘ is a finite set of the objects of C, such that the ground-set $V\left(A_i\right)$ of each object $A_i\in E$ is a finite set with at least two elements and $V\supseteq {\bigcup }_{i=1}^{m}V\left(A_i\right)$. To generalize the results on graph colourings to simple object systems we define, analogously as for graphs, that an additive induced-hereditary...

A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property 𝓟, a graph G ∈ 𝓟 is universal in 𝓟 if each member of 𝓟 is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in → H and we give a new proof of the existence of a universal graph in → H, for any finite graph...

For a given induced hereditary property 𝓟, a 𝓟-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property 𝓟. We consider the effectiveness of on-line 𝓟-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function of any stingy on-line 𝓟-coloring algorithm. In the class of generalized...

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number $\chi {*}_r\left(G\right)$ of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that $\chi {*}_r\left(Pₙ\right)<3log₂n$ for n ≥ 2. Here we show...

For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c : V (G) → N+ such that |c(u) − c(v)| ≥ 2 for each edge {u, v} ∈ E(H) and |c(u) − c(v)| ≥ 1 for each edge {u, v} ∈ E(G). The backbone chromatic number BBC(G,H) is the smallest integer k such that there exists a backbone coloring with maxv∈V (G) c(v) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.

An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees...

We provide the list of all paths with at most $16$ arcs with the property that if a graph $G$ admits an orientation $\overrightarrow{G}$ such that one of the paths in our list admits no homomorphism to $\overrightarrow{G}$, then $G$ is $3$-colourable.