Circular choosability is rational

The circular choosability or circular list chromatic number of a graph is a list-version of the circular chromatic number, that was introduced by Mohar in 2002 and has been studied by several groups of authors since then. One of the nice properties that the circular chromatic number enjoys is that it is a rational number for all finite graphs G, and a fundamental question, posed by Zhu and reiterated by others, is whether the same holds for the circular choosability. In this paper we show that this is indeed the case.     

Dirac's map-color theorem for choosability

It is proved that the choice number of every graph G embedded on a surface of Euler genus ε ≥ 1 and ε ≠ 3 is at most the Heawood number and that the equality holds if and only if G contains the complete graph K_H(ε) as a subgraph. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 327–339, 1999     

Cubic Thue inequalities with negative discriminant

We give an upper bound for the solutions of the family of cubic Thue inequalities |x³+axy²+by³|?k when a is positive and larger than a certain value depending on b. For the case k=a+|b|+1 and a?360b⁴ we show that these inequalities have only trivial solutions. For the case k=a+|b|+1 and |b|=1,2, we solve these inequalities for all a?1. Our method is based on Padé approximations using Rickert's integrals. We also use a generalization of Legendre's theorem on continued fractions.     

A parametric family of quintic Thue equations

For an integral parameter we investigate the family of Thue equations

originating from Emma Lehmer's family of quintic fields, and show that for the only solutions are the trivial ones with or . Our arguments contain some new ideas in comparison with the standard methods for Thue families, which gives this family a special interest.

     

The total chromatic number of regular graphs of even order and high degree

The total chromatic number χ_T(G) of a graph G is the minimum number of colours needed to colour the edges and the vertices of G so that incident or adjacent elements have distinct colours. We show that if G is a regular graph of even order and , thenχ_T(G)Δ(G)+2.     

Quartic Thue equations

We will give upper bounds upon the number of integral solutions to binary quartic Thue equations. We will also study the geometric properties of a specific family of binary quartic Thue equations to establish sharper upper bounds.     

On a family of relative quartic Thue inequalities

We consider the relative Thue inequalities

|X⁴−t²X²Y²+s²Y⁴|?²|t|−²|s|−2,     

Fractional total colourings of graphs of high girth

Reed conjectured that for every ?>0 and Δ there exists g such that the fractional total chromatic number of a graph with maximum degree Δ and girth at least g is at most Δ+1+?. We prove the conjecture for Δ=3 and for even Δ?4 in the following stronger form: For each of these values of Δ, there exists g such that the fractional total chromatic number of any graph with maximum degree Δ and girth at least g is equal to Δ+1.     

On the chromatic number of random graphs

We consider random graphs G_n,p with fixed edge-probability p. We refine an argument of Bollobás to show that almost all such graphs have chromatic number equal to n/{2 log_b n ? 2 log_b log_b n + O(1)} where b = 1/(1 ? p).     

Adaptable choosability of planar graphs with sparse short cycles

Given a (possibly improper) edge colouring F of a graph G, a vertex colouring of G is adapted toF if no colour appears at the same time on an edge and on its two endpoints. A graph G is called (for some positive integer k) if for any list assignment L to the vertices of G, with |L(v)|≥k for all v, and any edge colouring F of G, G admits a colouring c adapted to F where c(v)∈L(v) for all v. This paper proves that a planar graph G is adaptably 3-choosable if any two triangles in G have distance at least 2 and no triangle is adjacent to a 4-cycle.     

On the resolution of relative Thue equations

An efficient algorithm is given for the resolution of relative Thue equations. The essential improvement is the application of an appropriate version of Wildanger's enumeration procedure based on the ellipsoid method of Fincke and Pohst.

Recently relative Thue equations have gained an important application, e.g., in computing power integral bases in algebraic number fields. The presented methods can surely be used to speed up those algorithms.

The method is illustrated by numerical examples.

     

Edge choosability of planar graphs without short cycles

In this paper we prove that if G is a planar graph with △= 5 and without 4-cycles or 6-cycles, then G is edge-6-choosable. This consequence together with known results show that, for each fixed k ∈{3,4,5,6}, a k-cycle-free planar graph G is edge-(△ 1)-choosable, where △ denotes the maximum degree of G.     

Distinguishing chromatic numbers of complements of Cartesian products of complete graphs

The distinguishing chromatic number of a graph, $G$, is the minimum number of colours required to properly colour the vertices of $G$ so that the only automorphism of $G$ that preserves colours is the identity. There are many classes of graphs for which the distinguishing chromatic number has been studied, including Cartesian products of complete graphs (Jerebic and Klav?ar, 2010). In this paper we determine the distinguishing chromatic number of the complement of the Cartesian product of complete graphs, providing an interesting class of graphs, some of which have distinguishing chromatic number equal to the chromatic number, and others for which the difference between the distinguishing chromatic number and chromatic number can be arbitrarily large.     

The complexity of nonrepetitive coloring

A coloring of a graph is nonrepetitive if the graph contains no path that has a color pattern of the form xx (where x is a sequence of colors). We show that determining whether a particular coloring of a graph is nonrepetitive is coNP-hard, even if the number of colors is limited to four. The problem becomes fixed-parameter tractable, if we only exclude colorings xx up to a fixed length k of x.