Starting from the famous Königsberg bridge problem which Euler described in 1736, we intend to show that some results obtained 180 years later by König are very close to Euler's discoveries.

Let $G_1$ and $G_2$ be copies of a graph $G$, and let $f:V\left(G_1\right)\to V\left(G_2\right)$ be a function. Then a functigraph $C(G,f)=(V,E)$ is a generalization of a permutation graph, where $V=V\left(G_1\right)\cup V\left(G_2\right)$ and $E=E\left(G_1\right)\cup E\left(G_2\right)\cup \{uv:u\in V\left(G_1\right),v\in V\left(G_2\right),v=f\left(u\right)\}$. In this paper, we study colorability and planarity of functigraphs.

In this paper Gallai’s inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let $₁,₂,...,ₖ$ (k ≥ 2) be additive induced-hereditary properties, $=₁\circ ₂\circ ...\circ ₖ$ and $\delta ={\sum }_{i=1}^k\delta {(}_i)$. Suppose that G is an -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless = ² or $G=K_{\delta +1}$. The generalization of Gallai’s inequality for -choice critical graphs is also presented.

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be additive hereditary properties of graphs. The generalized chromatic number ${\chi }_{}\left(\right)$ is defined as follows: ${\chi }_{}\left(\right)=n$ iff ⊆ ⁿ but ${⊊}^{n-1}$. We investigate the generalized chromatic numbers of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ and ₖ.

Let P be a graph property and r,s ∈ N, r ≥ s. A strong circular (P,r,s)-colouring of a graph G is an assignment f:V(G) → {0,1,...,r-1}, such that the edges uv ∈ E(G) satisfying |f(u)-f(v)| < s or |f(u)-f(v)| > r - s, induce a subgraph of G with the propery P. In this paper we present some basic results on strong circular (P,r,s)-colourings. We introduce the strong circular P-chromatic number of a graph and we determine the strong circular P-chromatic number of complete graphs for additive...

Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed...

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be hereditary properties of graphs. The generalized edge-chromatic number ${\rho }_{}^{\text{'}}\left(\right)$ is defined as the least integer n such that ⊆ n. We investigate the generalized edge-chromatic numbers of the properties → H, ₖ, ₖ, *ₖ, ₖ and ₖ.

Let P and Q be additive and hereditary graph properties, r, s ∈ N, r ≥ s, and [ℤr]s be the set of all s-element subsets of ℤr. An (r, s)-fractional (P,Q)-total coloring of G is an assignment h : V (G) ∪ E(G) → [ℤr]s such that for each i ∈ ℤr the following holds: the vertices of G whose color sets contain color i induce a subgraph of G with property P, edges with color sets containing color i induce a subgraph of G with property Q, and the color sets of incident vertices and edges are disjoint. If...

An additive and hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be two additive and hereditary graph properties and let r, s be integers such that r ≥ s Then an [...] fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set {1, 2, . . . , r} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph of property P, all...

Let P and Q be additive and hereditary graph properties and let r, s be integers such that r ≥ s. Then an r/s -fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set {1, 2, . . . , r} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph with property P, all edges of color i induce a subgraph with property Q and vertices and incident edges have been assigned disjoint sets of colors. The...

We prove: (1) that $c{h}_P\left(G\right)-{\chi }_P\left(G\right)$ can be arbitrarily large, where $c{h}_P\left(G\right)$ and ${\chi }_P\left(G\right)$ are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks’ and Gallai’s theorems.

For natural numbers k and n, where 2 ≤ k ≤ n, the vertices of a graph are labeled using the elements of the k-fold Cartesian product Iₙ × Iₙ × ... × Iₙ. Two particular graph constructions will be given and the graphs so constructed are called generalized matrix graphs. Properties of generalized matrix graphs are determined and their application to completely independent critical cliques is investigated. It is shown that there exists a vertex critical graph which admits a family of k completely independent...