Acyclic improper colourings of graphs with bounded maximum degree

For graphs of bounded maximum degree, we consider acyclic t-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic, and each colour class induces a graph with maximum degree at most t.We consider the supremum, over all graphs of maximum degree at most d, of the acyclic t-improper chromatic number and provide t-improper analogues of results by Alon, McDiarmid and Reed [N. Alon, C.J.H. McDiarmid, B. Reed, Acyclic coloring of graphs, Random Structures Algorithms 2 (3) (1991) 277-288] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2004) 163-182].     

Acyclic edge colouring of planar graphs without short cycles

Let G=(V,E) be any finite graph. A mapping C:E→[k] is called an acyclic edgek-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges which have colour i or j, is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G, denoted by .In 2001, Alon et al. conjectured that for any graph G it holds that ; here Δ(G) stands for the maximum degree of G.In this paper we prove this conjecture for planar graphs with girth at least 5 and for planar graphs not containing cycles of length 4,6,8 and 9. We also show that if G is planar with girth at least 6. Moreover, we find an upper bound for the acyclic chromatic index of planar graphs without cycles of length 4. Namely, we prove that if G is such a graph, then .     

Acyclic colorings of graphs with bounded degree

A k-coloring (not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k-colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5-coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2-coloring in which each color class induces a graph with maximum degree at most 3 is NP-complete, even for graphs with maximum degree 5. We also give a linear-time algorithm for an acyclic t-improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.     

Improper colouring of (random) unit disk graphs

For any graph G, the k-improper chromatic numberχ^k(G) is the smallest number of colours used in a colouring of G such that each colour class induces a subgraph of maximum degree k. We investigate χ^k for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed [Colouring proximity graphs in the plane, Discrete Math. 199(1-3) (1999) 123-137], McDiarmid [Random channel assignment in the plane, Random Structures Algorithms 22(2) (2003) 187-212], and McDiarmid and Müller [On the chromatic number of random geometric graphs, submitted for publication].     

Graph colourings with forbidden k-coloured subgraphs

Abstract

For a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G.     

Generalised acyclic edge colourings of graphs with large girth

The r-acyclic edge chromatic number of a graph G is the minimum number of colours required to colour the edges of G in such a way that adjacent edges receive different colours and every cycle C receives at least min{|C|,r} colours. We prove that for any integer r?4, the r-acyclic edge chromatic number of any graph G with maximum degree Δ and with girth at least 3(r-1)Δ is at most 6(r-1)Δ.     

Acyclic edge coloring of planar graphs without adjacent cycles

A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

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.     

Acyclic edge coloring of 2‐degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

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{]}$.     

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.     

Frugal, acyclic and star colourings of graphs

Given a graph G=(V,E), a vertex colouring of V is t-frugal if no colour appears more than t times in any neighbourhood and is acyclic if each of the bipartite graphs consisting of the edges between any two colour classes is acyclic. For graphs of bounded maximum degree, Hind et al. (1997) [14] studied proper t-frugal colourings and Yuster (1998) [22] studied acyclic proper 2-frugal colourings. In this paper, we expand and generalise this study.     

Acyclic Edge Coloring of Triangle‐Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G) ? Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|?1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′(G) ? Δ + 3. Triangle‐free planar graphs satisfy Property A. We infer that a′(G) ? Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory     

A result on the total colouring of powers of cycles

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. The Total Colouring Conjecture (TCC) states that for every simple graph G, χ_T(G)?Δ(G)+2. This work verifies the TCC for powers of cycles even and 2<k<n/2, showing that there exists and can be polynomially constructed a (Δ(G)+2)-total colouring for these graphs.     

A unified approach to distance-two colouring of graphs on surfaces

In this paper we introduce the notion of Σ-colouring of a graph G: For given subsets Σ(v) of neighbours of v, for every v∈V (G), this is a proper colouring of the vertices of G such that, in addition, vertices that appear together in some Σ(v) receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of graphs embedded in a surface. We prove a general result for graphs embeddable in a fixed surface, which implies asymptotic versions of Wegner’s and Borodin’s Conjecture on the planar version of these two colourings. Using a recent approach of Havet et al., we reduce the problem to edge-colouring of multigraphs, and then use Kahn’s result that the list chromatic index is close to the fractional chromatic index. Our results are based on a strong structural lemma for graphs embeddable in a fixed surface, which also implies that the size of a clique in the square of a graph of maximum degree Δ embeddable in some fixed surface is at most $ \frac{3} {2}\Delta $ plus a constant.     

Acyclic List Edge Coloring of Graphs

A proper edge coloring of a graph is said to be acyclic if any cycle is colored with at least three colors. An edge-list L of a graph G is a mapping that assigns a finite set of positive integers to each edge of G. An acyclic edge coloring ? of G such that for any is called an acyclic L-edge coloring of G. A graph G is said to be acyclically k-edge choosable if it has an acyclic L‐edge coloring for any edge‐list L that satisfies for each edge e. The acyclic list chromatic index is the least integer k such that G is acyclically k‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.     

On the Relaxed Colouring Game and the Unilateral Colouring Game

In the paper we introduce the new game—the unilateral \({\mathcal{P}}\) -colouring game which can be used as a tool to study the r-colouring game and the (r, d)-relaxed colouring game. Let be given a graph G, an additive hereditary property \({\mathcal {P}}\) and a set C of r colours. In the unilateral \({\mathcal {P}}\) -colouring game similarly as in the r-colouring game, two players, Alice and Bob, colour the uncoloured vertices of the graph G, but in the unilateral \({\mathcal {P}}\) -colouring game Bob is more powerful than Alice. Alice starts the game, the players play alternately, but Bob can miss his move. Bob can colour the vertex with an arbitrary colour from C, while Alice must colour the vertex with a colour from C in such a way that she cannot create a monochromatic minimal forbidden subgraph for the property \({\mathcal {P}}\) . If after |V(G)| moves the graph G is coloured, then Alice wins the game, otherwise Bob wins. The \({\mathcal {P}}\) -unilateral game chromatic number, denoted by \({\chi_{ug}^\mathcal {P}(G)}\) , is the least number r for which Alice has a winning strategy for the unilateral \({\mathcal {P}}\) -colouring game with r colours on G. We prove that the \({\mathcal {P}}\) -unilateral game chromatic number is monotone and is the upper bound for the game chromatic number and the relaxed game chromatic number. We give the winning strategy for Alice to play the unilateral \({\mathcal {P}}\) -colouring game. Moreover, for k ≥  2 we define a class of graphs \({\mathcal {H}_k =\{G|{\rm every \;block \;of\;}G \; {\rm has \;at \;most}\; k \;{\rm vertices}\}}\) . The class \({\mathcal {H}_k }\) contains, e.g., forests, Husimi trees, line graphs of forests, cactus graphs. Let \({\mathcal {S}_d}\) be the class of graphs with maximum degree at most d. We find the upper bound for the \({\mathcal {S}_2}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_3}\) and we study the \({\mathcal {S}_d}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_4}\) for \({d \in \{2,3\}}\) . As the conclusion from these results we obtain the result for the d-relaxed game chromatic number: if \({G \in \mathcal {H}_k}\) , then \({\chi_g^{(d)}(G) \leq k + 2-d}\) , for \({k \in \{3, 4\}}\) and \({d \in \{0, \ldots, k-1\}}\) . This generalizes a known result for trees.     

Acyclic edge coloring of graphs with maximum degree 4

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a′(G)?Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)?4, with the additional restriction that m?2n?1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m?2n, when Δ(G)?4. It follows that for any graph G if Δ(G)?4, then a′(G)?7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009     

Improved upper bounds on acyclic edge colorings

An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors.The acyclic chromatic index of a graph G,denoted by a′(G),is the minimum number k such that there is an acyclic edge coloring using k colors.It is known that a′(G)≤16△for every graph G where △denotes the maximum degree of G.We prove that a′(G)13.8△for an arbitrary graph G.We also reduce the upper bounds of a′(G)to 9.8△and 9△with girth 5 and 7,respectively.