Search

We classify all possible zero-divisor graphs of a particular family of quotients of $$\mathbf{Z}_4[x,y,w,z]$$ . As the 90 quotients vary, we obtain a total of 7 graphs, corresponding to seven isomorphism classes, and one of these graphs provides a new example which contradicts Beck's conjecture on the chromatic number of a zero-divisor graph. The algebraic analysis is strongly supported by the combinatorial setting, as already shown in a previous paper, where the graph-theoretical tools were presented and successfully applied to $$\mathbf{Z}_4[x,y,z]$$ -therefore, the just smaller case-in order to get a deeper knowledge of the classical counterexample to Beck's conjecture. [ABSTRACT FROM AUTHOR]

A graph or more generally a multigraph can be interpreted as a family of stars-one star for each vertex-which adequately intersect on certain edges, so as to generate a global adjacency structure. An edge colouring can be read as an injective assignment of colours to each star, enjoying a 'compatibility' property on adjacent vertices: for, any two intersecting stars must obviously get the same colour on each pair of overlapping edges (stars of multigraphs may have more than one overlap). The above interpretation justifies some key definitions which make an edge colouring rather similar to a differentiable atlas on a manifold. In the case of simple graphs, the distinction between class 1 and class 2 becomes the distinction between orientable and non-orientable atlases. In particular, $$k$$ -critical graphs with $$2\le k\le 3$$ are shown to be, in most cases, the result of an identification of extremal edges or vertices which is analogous to the topological identification yielding the Möbius strip from the rectangular strip. Moving along the strip is equivalent to transmitting a fixed colour across the local charts (stars) of the graph. Accordingly, we revisit the known classification of small 3-critical graphs, with a specific stress on the various types of graphs which lose orientability (i.e. become critical) after the identification of their extremes. [ABSTRACT FROM AUTHOR]

We analyse 3-subset difference families of Z 2 d +1⊕ Z 2 d +1 arising as reductions (mod 2 d+1) of particular families of 3-subsets of Z⊕ Z. The latter structures, namely perfect d-families, can be viewed as 2-dimensional analogues of difference triangle sets having the least scope. Indeed, every perfect d-family is a set of base blocks which, under the natural action of the translation group Z⊕ Z, cover all edges {( x, y),( x′, y′)} such that | x− x′|, | y− y′|≤ d. In particular, such a family realises a translation invariant ( G, K 3)-design, where V( G)= Z⊕ Z and the edges satisfy the above constraint. For that reason, we regard perfect families as part of the hereby defined translation designs, which comprise and slightly generalise many structures already existing in the literature. The geometric context allows some suggestive additional definitions. The main result of the paper is the construction of two infinite classes of d-families. Furthermore, we provide two sporadic examples and show that a d-family may exist only if d≡0,3,8,11 (mod 12). [ABSTRACT FROM AUTHOR]

We address some complexity questions related to the arc-coloring of directed hypergraphs. Such hypergraphs arise as a generalization of digraphs, by allowing the tail of each arc to consist of more than one node. The related arc-coloring extends the notion of digraph arc-coloring, which has been studied by diverse authors. Using two classical results we easily prove that the optimal coloring of a digraph, as well as the 2-coloring test for every directed hypergraph, require polynomial time. Instead, the k-colorability problem for some fixed degree d is shown to be NP-complete if k⩾d⩾2 and k⩾3, even if the input is restricted to the so-called non-overlapping hypergraphs. We also describe a sub-class of hypergraphs for which the 3-colorability test is polynomially decidable. Some results are rephrased and proved using suitable adjacency matrices, namely walls. [Copyright &y& Elsevier]

Discusses the Tchebycheff psi function. Derivation of equations; Interpretation of the psi function.