Search

The union vertex-distinguishing chromatic index χ ∪ ′ (G) of a graph G is the smallest natural number k such that the edges of G can be assigned nonempty subsets of [ k ] so that the union of the subsets assigned to the edges incident to each vertex is different. We prove that χ ∪ ′ (G) ∈ { ⌈ log 2 ⁡ (n + 1) ⌉ , ⌈ log 2 ⁡ (n + 1) ⌉ + 1 } for any graph G on n vertices without a component of order at most 2. This answers a question posed by Bousquet, Dailly, Duchêne, Kheddouci and Parreau, and independently by Chartrand, Hallas and Zhang. [ABSTRACT FROM AUTHOR]

We almost completely solve a number of problems related to a concept called majority colouring recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number k, the smallest number m = m(k) such that every digraph can be coloured with m colours where each vertex has the same colour as at most a 1/k proportion of its out-neighbours. We show that m(k) ∈ {2k − 1,2k}. We also prove a result supporting the conjecture that m(2) = 3. Moreover, we prove similar results for a more general concept called majority choosability. [ABSTRACT FROM AUTHOR]

Given an edge coloring of a graph with a set of m colors, we say that the graph is exactly m-colored if each of the colors is used. In 1999, Stacey and Weidl, partially resolving a conjecture of Erickson from 1994, showed that for a fixed natural number [ABSTRACT FROM AUTHOR]

Given an edge colouring of a graph with a set of m colours, we say that the graph is exactly m-coloured if each of the colours is used. We consider edge colourings of the complete graph on $\mathbb{N}$ with infinitely many colours and show that either one can find an exactly m-coloured complete subgraph for every natural number m or there exists an infinite subset X ⊂ $\mathbb{N}$ coloured in one of two canonical ways: either the colouring is injective on X or there exists a distinguished vertex v in X such that X\{v} is 1-coloured and each edge between v and X\{v} has a distinct colour (all different to the colour used on X\{v}). This answers a question posed by Stacey and Weidl in 1999. The techniques that we develop also enable us to resolve some further questions about finding exactly m-coloured complete subgraphs in colourings with finitely many colours. [ABSTRACT FROM AUTHOR]