Cost colourings of hypergraphs

Some aspects of the cost colouring of hypergraphs are considered in the paper. A generalisation of the well-known Brook's theorem for a cost colouring of hypergraphs is proved. Moreover, a relation between the minimal cost of a colouring of a hypergraph with a set of costs which produce an arithmetic sequence and a number of edges of this hypergraph is investigated.     

Fractional matchings and covers in infinite hypergraphs

A strong version of the duality theorem of linear programming is proved for fractional covers and matchings in countable graphs. It is conjectured to hold for general hypergraphs. In Section 2 we show that in countable hypergraphs there does not necessarily exist a maximal matchable set, contrary to the situation in graphs.     

Dichotomy theorems for countably infinite dimensional analytic hypergraphs

We give classical proofs, strengthenings, and generalizations of Lecomte’s characterizations of analytic ω-dimensional hypergraphs with countable Borel chromatic number.     

Optimal fractional matchings and covers in infinite hypergraphs: Existence and duality

We study fractional matchings and covers in infinite hypergraphs, paying particular attention to the following questions: Do fractional matchings (resp. covers) of maximal (resp. minimal) size exist? Is there equality between the supremum of the sizes of fractional matchings and the infimum of the sizes of fractional covers? (This is called weak duality.) Are there a fractional matching and a fractional cover that satisfy the complementary slackness conditions of linear programming? (This is called strong duality.) In general, the answers to all these questions are negative, but for certain classes of infinite hypergraphs (classified according to edge cardinalities and vertex degrees) we obtain positive results. We also consider the question of the existence of optimal fractional matchings and covers that assume rational values.     

Recolouring-resistant colourings

We study colourings of graphs with the property that the number of used colours cannot be reduced by applying some recolouring operation. A well-studied example of such colourings are b-colourings, which were introduced by Irving and Manlove [R.W. Irving, D.F. Manlove, The b-chromatic number of a graph, Discrete Appl. Math. 91 (1999) 127-141]. Given a graph and a colouring, a recolouring operation specifies a set of vertices of the graph on which the colouring can be changed. We consider two such operations: One which allows the recolouring of all vertices within some given distance of some colour class, and another which allows the recolouring of all vertices that belong to one of a given number of colour classes. Our results extend known results concerning b-colourings and the associated b-chromatic number.     

Ordered colourings of graphs

An ordered colouring of a graph with k colours is a vertex colouring with colours {1, 2,…,k} such that each vertex coloured j is joined to at least one vertex-of colour i for each i less than j. Examples of ordered colourings are those produced by the greedy colouring algorithm. Some properties are investigated of τ(G), the maximum k for which the graph G has an ordered k-colouring (in fact τ(G) is an upper bound for the number of colours used by the greedy algorithm). It is shown that if G has order n, then $\text{τ(G) + τ(}\text{G}\text{) ≤ [}\text{(5n + 2)}\text{4}\text{]}$.     

Interval hypergraphs and D-interval hypergraphs

A hypergraph $\text{H = (V,}\text{E}\text{)}$ is called an interval hypergraph if there exists a one-to-one function ? mapping the elements of V to points on the real line such that for each edge E, there is an interval I, containing the images of all elements of E, but not the images of any elements not in E₁. The difference hypergraph D(H) determined by H is formed by adding to $\text{E}$ all nonempty sets of the form E₁ ? E₁, where E₁ and E₁ are edges of HH is said to be a D-interval hypergraph if D(H) is an interval hypergraph. A forbidden subhypergraph characterization of D-interval hypergraphs is given. By relating D-interval hypergraphs to dimension theory for posets, we determine all 3-irreducible posets of length one.     

Fractional and integral colourings

LetG=(V, E) be an undirected graph andc any vector in ℤ ^V(G) ₊. Denote byχ(G _c) (resp.η(G _c)) the chromatic number (resp. fractional chromatic number) ofG with respect toc. We study graphs for whichχ(G _c)−[η(G _c)]⩽1. We show that for the class of graphs satisfyingχ(G _c)=[η(G _c)] (a class generalizing perfect graphs), an analogue of the Duplication Lemma does not hold. We also describe a 2-vertex cut decomposition procedure related to the integer decomposition property. We use this procedure to show thatχ(G _c)=[η(G _c)] for series-parallel graphs andχ(G _c)⩽[η(G _c)]+1 for graphs that do not have the 4-wheel as a minor. The work of this author was supported by the Natural Sciences and Engineering Research Council of Canada (NSERCC) under grant A9126.     

Perfect colourings of cyclotomic integers

Perfect colourings of the rings of cyclotomic integers of class number one are studied. It is shown that all colourings induced by ideals (q) are chirally perfect, and vice versa. A necessary and sufficient condition for a colouring to be perfect is obtained, depending on the factorisation of q. This result yields the colour symmetry group H in general. Furthermore, the colour preserving group K is determined in all but finitely many cases. An application to colourings of quasicrystals is given.     

List colourings of planar graphs

A graph G = G(V, E) is called L-list colourable if there is a vertex colouring of G in which the colour assigned to a vertex v is chosen from a list L(v) associated with this vertex. We say G is k-choosable if all lists L(v) have the cardinality k and G is L-list colourable for all possible assignments of such lists. There are two classical conjectures from Erd s, Rubin and Taylor 1979 about the choosability of planar graphs:

every planar graph is 5-choosable and,

there are planar graphs which are not 4-choosable.

We will prove the second conjecture.     

On defected colourings of graphs

Abstract A k-edge-coloring f of a connected graph G is a （A1, A2, , A）-defected k-edge-coloring if there is a smallest integer/ with 1 _ /3 _〈 k - i such that the multiplicity of each color j E {1,2,... ,/3} appearing at a vertex is equal to Aj _〉 2, and each color of {/3 -}- 1,/3 - 2, - , k} appears at some vertices at most one time. The （A1, A2,, A/）-defected chromatic index of G, denoted as X （A1, A2,, A/; G）, is the smallest number such that every （A1,A2,-.., A/）-defected t-edge-coloring of G holds t _〉 X（A1, A2 A;; G）. We obtain A（G） X（A1, ）2, , A/; G） ＋ -- （Ai - 1） _〈 /k（G） 1, and introduce two new chromatic indices of G i=1 as： the vertex pan-biuniform chromatic index X pb （G）, and the neighbour vertex pan-biuniform chromatic index Xnpb（G）, and furthermore find the structure of a tree T having X pb （T） =1.     

Essentially subnormal operators

An operator is essentially subnormal if its image in the Calkin algebra is subnormal. We shall characterize the essentially subnormal operators as those operators with an essentially normal extension. In fact, it is shown that an essentially subnormal operator has an extension of the form ``normal plus compact'.

The essential normal spectrum is defined and is used to characterize the essential isometries. It is shown that every essentially subnormal operator may be decomposed as the direct sum of a subnormal operator and some irreducible essentially subnormal operators. An essential version of Putnam's Inequality is proven for these operators. Also, it is shown that essential normality is a similarity invariant within the class of essentially subnormal operators. The class of essentially hyponormal operators is also briefly discussed and several examples of essentially subnormal operators are given.

     

Threshold hypergraphs

This paper deals with three generalizations of threshold graphs to hypergraphs proposed by M. Ch. Golumbic. Answering a question of M. Ch. Golumbic we show that these three definitions are not equivalent. The main results of the paper are Theorems 2.5 and 2.6 which characterize hypergraphs satisfying the most general of above definitions.