Complete and almost complete minors in double-critical 8-chromatic graphs.
Complete and pseudocomplete colourings of a graph
Conditions for β-perfectness
A β-perfect graph is a simple graph G such that χ(G') = β(G') for every induced subgraph G' of G, where χ(G') is the chromatic number of G', and β(G') is defined as the maximum over all induced subgraphs H of G' of the minimum vertex degree in H plus 1 (i.e., δ(H)+1). The vertices of a β-perfect graph G can be coloured with χ(G) colours in polynomial time (greedily). The main purpose of this paper is to give necessary and sufficient conditions, in terms of forbidden induced subgraphs,...
Constrained Colouring and σ-Hypergraphs
A constrained colouring or, more specifically, an (α, β)-colouring of a hypergraph H, is an assignment of colours to its vertices such that no edge of H contains less than α or more than β vertices with different colours. This notion, introduced by Bujtás and Tuza, generalises both classical hypergraph colourings and more general Voloshin colourings of hypergraphs. In fact, for r-uniform hypergraphs, classical colourings correspond to (2, r)-colourings while an important instance of Voloshin colourings...
Continuation of a 3-coloring from a 7-face onto a plane graph without .
Cores and shells of graphs
The -core of a graph , , is the maximal induced subgraph such that , if it exists. For , the -shell of a graph is the subgraph of induced by the edges contained in the -core and not contained in the -core. The core number of a vertex is the largest value for such that , and the maximum core number of a graph, , is the maximum of the core numbers of the vertices of . A graph is -monocore if . This paper discusses some basic results on the structure of -cores and -shells....
Countable 1-transitive coloured linear orderings II
This paper gives a structure theorem for the class of countable 1-transitive coloured linear orderings for a countably infinite colour set, concluding the work begun in [1]. There we gave a complete classification of these orders for finite colour sets, of which there are ℵ₁. For infinite colour sets, the details are considerably more complicated, but many features from [1] occur here too, in more marked form, principally the use (now essential it seems) of coding trees, as a means of describing...
Countable homogeneous coloured partial orders [Book]
Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices
We prove that for any , there exists an infinite family of graphs such that for all and for all . These counterexamples to Hedetniemi’s conjecture show that the Boolean lattice of exponential graphs with as a base is infinite for .
Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties
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 for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (₁,₂,...,ₙ)-partitionable graphs exist if and only if and are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ 1,2,...,n.
Critical subgraphs of a random graph.
Crossings, colorings, and cliques.
Cubic graphs without a Petersen minor have nowhere-zero 5-flow.
Cyclic Crystallizations of Spheres.
Cyclic labellings with constraints at two distances.
Cyclically 5-edge connected non-bicritical critical snarks
Snarks are bridgeless cubic graphs with chromatic index χ' = 4. A snark G is called critical if χ'(G-{v,w}) = 3, for any two adjacent vertices v and w. For any k ≥ 2 we construct cyclically 5-edge connected critical snarks G having an independent set I of at least k vertices such that χ'(G-I) = 4. For k = 2 this solves a problem of Nedela and Skoviera [6].
Decomposing a planar graph into a forest and a subgraph of restricted maximum degree.
Decomposition of complete bipartite graphs into factors with given radii
Decomposition of complete bipartite graphs into factors with given diameters
Decomposition of spheres in Hilbert spaces