In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is ${}^I(4,5)$, the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of ${}^I(4,5)$ are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have...

The $k$-core of a graph $G$, $C_k\left(G\right)$, is the maximal induced subgraph $H\subseteq G$ such that $\delta \left(G\right)\ge k$, if it exists. For $k>0$, the $k$-shell of a graph $G$ is the subgraph of $G$ induced by the edges contained in the $k$-core and not contained in the $(k+1)$-core. The core number of a vertex is the largest value for $k$ such that $v\in C_k\left(G\right)$, and the maximum core number of a graph, $\widehat{C}\left(G\right)$, is the maximum of the core numbers of the vertices of $G$. A graph $G$ is $k$-monocore if $\widehat{C}\left(G\right)=\delta \left(G\right)=k$. This paper discusses some basic results on the structure of $k$-cores and $k$-shells....

A graph is called splitting if there is a 0-1 labelling of its vertices such that for every infinite set C of natural numbers there is a sequence of labels along a 1-way infinite path in the graph whose restriction to C is not eventually constant. We characterize the countable splitting graphs as those containing a subgraph of one of three simple types.

Let ₁,₂,...,ₙ be graph properties, a graph G is said to be uniquely (₁,₂, ...,ₙ)-partitionable if there is exactly one (unordered) partition V₁,V₂,...,Vₙ of V(G) such that $G\left[V_i\right]{\in }_i$ for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (₁,₂,...,ₙ)-partitionable graphs exist if and only if ${}_i$ and ${}_j$ are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ 1,2,...,n.

Let V be a finite vertex set and let (, +) be a finite abelian group. An -labeled and reversible 2-structure defined on V is a function g : (V × V) (v, v) : v ∈ V → such that for distinct u, v ∈ V, g(u, v) = −g(v, u). The set of -labeled and reversible 2-structures defined on V is denoted by ℒ(V, ). Given g ∈ ℒ(V, ), a subset X of V is a clan of g if for any x, y ∈ X and v ∈ V X, g(x, v) = g(y, v). For example, ∅, V and v (for v ∈ V) are clans of g, called trivial. An element g of ℒ(V, ) is primitive...