The total-chromatic number of some families of snarks

The total-chromatic numberχ_T(G) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. It is known that the problem of determining the total-chromatic number is NP-hard, and it remains NP-hard even for cubic bipartite graphs. Snarks are simple connected bridgeless cubic graphs that are not 3-edge-colourable. In this paper, we show that the total-chromatic number is 4 for three infinite families of snarks, namely, the Flower Snarks, the Goldberg Snarks, and the Twisted Goldberg Snarks. This result reinforces the conjecture that all snarks have total-chromatic number 4. Moreover, we give recursive procedures to construct a total-colouring that uses 4 colours in each case.     

The circular chromatic number of hypergraphs

A generalization of the circular chromatic number to hypergraphs is discussed. In particular, it is indicated how the basic theory, and five equivalent formulations of the circular chromatic number of graphs, can be carried over to hypergraphs with essentially the same proofs.     

The game chromatic index of wheels

We prove that the game chromatic index of n-wheels is n for n≥6.     

A survey on snarks and new results: Products,reducibility and a computer search

In this paper we survey recent results and problems of both theoretical and algorithmic character on the construction of snarks—non-trivial cubic graphs of class two, of cyclic edge-connectivity at least 4 and with girth ≥ 5. We next study the process, also considered by Cameron, Chetwynd, Watkins, Isaacs, Nedela, and Sˇkoviera, of splitting a snark into smaller snarks which compose it. This motivates an attempt to classify snarks by recognizing irreducible and prime snarks and proving that all snarks can be constructed from them. As a consequence of these splitting operations, it follows that any snark (other than the Petersen graph) of order ≤ 26 can be built as either a dot product or a square product of two smaller snarks. Using a new computer algorithm we have confirmed the computations of Brinkmann and Steffen on the classification of all snarks of order less than 30. Our results recover the well-known classification of snarks of order not exceeding 22. Finally, we prove that any snark G of order ≤ 26 is almost Hamiltonian, in the sense that G has at least one vertex v for which G \ v is Hamiltonian. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 57–86, 1998     

On the fractional chromatic index of a graph and its complement

Jensen and Toft conjectured that for a graph with an even number of vertices, either the minimum number of colours in a proper edge colouring is equal to the maximum vertex degree, or this is true in its complement. We prove a fractional version of this conjecture.     

General neighbour-distinguishing index via chromatic number

An edge colouring of a graph G without isolated edges is neighbour-distinguishing if any two adjacent vertices have distinct sets consisting of colours of their incident edges. The general neighbour-distinguishing index of G is the minimum number of colours in a neighbour-distinguishing edge colouring of G. Gy?ri et al. [E. Gy?ri, M. Horňák, C. Palmer, M. Wo?niak, General neighbour-distinguishing index of a graph, Discrete Math. 308 (2008) 827-831] proved that provided G is bipartite and gave a complete characterisation of bipartite graphs according to their general neighbour-distinguishing index. The aim of this paper is to prove that if χ(G)≥3, then . Therefore, if log₂χ(G)∉Z, then .     

The circular chromatic index of some class 2 graphs

In this paper we consider the circular edge coloring of four families of Class 2 graphs. For the first two we establish the exact value of the circular chromatic index. For the next two, namely Goldberg and Isaacs snarks we derive an upper bound on this graph invariant. Finally, we consider the computational complexity of some problems related to circular edge coloring.     

Circular game chromatic number of graphs

In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χ_cg(G) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χ_cg(G)≤2χ_a(G)(χ_a(G)+1), where χ_a(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles.     

A note on the edge cover chromatic index of multigraphs

Let G be a multigraph with vertex set V(G). An edge coloring C of G is called an edge-cover-coloring if each color appears at least once at each vertex v∈V(G). The maximum positive integer k such that G has a k-edge-cover-coloring is called the edge cover chromatic index of G and is denoted by . It is well known that , where μ(v) is the multiplicity of v and δ(G) is the minimum degree of G. We improve this lower bound to δ(G)−1 when 2≤δ(G)≤5. Furthermore we show that this lower bound is best possible.     

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.     

Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers

For a graph G on n vertices with chromatic number χ(G), the Nordhaus-Gaddum inequalities state that , and . Much analysis has been done to derive similar inequalities for other graph parameters, all of which are integer-valued. We determine here the optimal Nordhaus-Gaddum inequalities for the circular chromatic number and the fractional chromatic number, the first examples of Nordhaus-Gaddum inequalities where the graph parameters are rational-valued.     

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).     

On Vizing’s bound for the chromatic index of a multigraph

Two of the basic results on edge coloring are Vizing’s Theorem [V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian); V.G. Vizing, The chromatic class of a multigraph, Kibernetika (Kiev) 3 (1965) 29-39 (in Russian). English translation in Cybernetics 1 32-41], which states that the chromatic index χ^′(G) of a (multi)graph G with maximum degree Δ(G) and maximum multiplicity μ(G) satisfies Δ(G)≤χ^′(G)≤Δ(G)+μ(G), and Holyer’s Theorem [I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718-720], which states that the problem of determining the chromatic index of even a simple graph is NP-hard. Hence, a good characterization of those graphs for which Vizing’s upper bound is attained seems to be unlikely. On the other hand, Vizing noticed in the first two above-cited references that the upper bound cannot be attained if Δ(G)=2μ(G)+1≥5. In this paper we discuss the problem: For which values Δ,μ does there exist a graph G satisfying Δ(G)=Δ, μ(G)=μ, and χ^′(G)=Δ+μ.     

On the chromatic numbers of Steiner triple systems

Geometric properties are used to determine the chromatic number of AG(4, 3) and to derive some important facts on the chromatic number of PG(n, 2). It is also shown that a 4-chromatic STS(v) exists for every admissible order v ≥ 21. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 1–10, 1999     

Some bounds on the injective chromatic number of graphs

We give some bounds on the injective chromatic number.     

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.