Search

We strengthen a result of Dross et al. (2017) that the vertex set of every triangle-free planar graph can be decomposed into a set that induces a forest and a set that induces a forest with maximum degree at most 5, showing that 5 can be replaced by 3. [ABSTRACT FROM AUTHOR]

The reconfiguration graph R k (G) for the k -colorings of a graph G has as vertex set the set of all possible k -colorings of G and two colorings are adjacent if they differ in the color of exactly one vertex of G. Let d , k ≥ 1 be integers such that k ≥ d + 1. We prove that for every ϵ > 0 and every graph G with n vertices and maximum average degree d − ϵ , R k (G) has diameter O (n (log ⁡ n) d − 1). This significantly strengthens several existing results. [ABSTRACT FROM AUTHOR]

Given a graph G = ( V , E ) and a proper vertex colouring of G , a Kempe chain is a subset of V that induces a maximal connected subgraph of G in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by exchanging the colours of vertices in a Kempe chain. Two colourings are Kempe equivalent if each can be obtained from the other by a series of Kempe changes. A conjecture of Mohar asserts that, for k ≥ 3 , all k -colourings of connected k -regular graphs that are not complete are Kempe equivalent. We address the case k = 3 by showing that all 3 -colourings of a connected cubic graph G are Kempe equivalent unless G is the complete graph K 4 or the triangular prism. [ABSTRACT FROM AUTHOR]

Abstract The reconfiguration graph R k (G) of the k -colourings of a graph G has as vertex set the set of all possible k -colourings of G and two colourings are adjacent if they differ on the colour of exactly one vertex. We give a short proof of the following theorem of Bousquet and Perarnau (European Journal of Combinatorics , 2016). Let d and k be positive integers, k ≥ d + 1. For every ϵ > 0 and every graph G with n vertices and maximum average degree d − ϵ , there exists a constant c = c (d , ϵ) such that R k (G) has diameter O (n c). Our proof can be transformed into a simple polynomial time algorithm that finds a path between a given pair of colourings in R k (G). [ABSTRACT FROM AUTHOR]

A subset A of [ n ] = { 1 , ... , n } is k - separated if, when the elements of [ n ] are considered on a circle, between every two elements of A there are at least k elements of [ n ] that are not in A. A family A of sets is intersecting if every two sets in A intersect. We give a short proof of a remarkable result of Talbot (2003), stating that if n ≥ (k + 1) r and A is an intersecting family of k -separated r -element subsets of [ n ] , then | A | ≤ n − k r − 1 r − 1 . This bound is best possible. [ABSTRACT FROM AUTHOR]

The reconfiguration graph R k (G) for the k -colorings of a graph G has as vertices all possible k -colorings of G and two colorings are adjacent if they differ in the color of exactly one vertex. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that for a planar graph G with n vertices, R 12 (G) has diameter at most 6 n , and if G is triangle-free, then R 8 (G) has diameter at most 4 n. We use a list coloring technique inspired by results of Thomassen to improve on the number of colors, showing that for a planar graph G with n vertices, R 10 (G) has diameter at most 8 n , and if G is triangle-free, then R 7 (G) has diameter at most 7 n. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a connected graph with maximum degree k ≥ 3 distinct from K k + 1. Given integers s ≥ 2 and p 1 , ... , p s ≥ 0 , G is said to be (p 1 , ... , p s) -partitionable if there exists a partition of V into sets V 1 , ... , V s such that G [ V i ] is p i -degenerate for i ∈ { 1 , ... , s }. In this paper, we prove that we can find a (p 1 , ... , p s) -partition of G in O (| V | + | E |) -time whenever 1 ≥ p 1 , ... , p s ≥ 0 and ∑ i = 1 s p i ≥ k − s. This generalizes a result of Bonamy et al. (2017) and can be viewed as an algorithmic extension of Brooks' Theorem and several results on vertex arboricity of graphs of bounded maximum degree. We also prove that deciding whether G is (p , q) -partitionable is NP -complete for every k ≥ 5 and pairs of non-negative integers (p , q) such that (p , q) ≠ (1 , 1) and p + q = k − 3. This resolves an open problem of Bonamy et al. (2017). Combined with results of Borodin et al. (2000), Yang and Yuan (2006) and Wu et al. (1996), it also settles the complexity of deciding whether a graph with bounded maximum degree can be partitioned into two subgraphs of prescribed degeneracy. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with maximum degree Δ ≥ 3 distinct from K Δ + 1. Generalizing Brooks' Theorem, Borodin and independently Bollobás and Manvel, proved that if p 1 , ... , p s are non-negative integers such that p 1 + ⋯ + p s ≥ Δ − s , then G admits a vertex partition into parts A 1 , ... , A s such that, for 1 ≤ i ≤ s , G [ A i ] is p i -degenerate. Here we show that such a partition can be performed in time O (n + m). This generalizes previous results that treated subcases of a conjecture of Abu-Khzam et al. (2020) which our result settles in full. [ABSTRACT FROM AUTHOR]

Abstract Let G be a graph with a vertex colouring α. Let a and b be two colours. Then a connected component of the subgraph induced by those vertices coloured either a or b is known as a Kempe chain. A colouring of G obtained from α by swapping the colours on the vertices of a Kempe chain is said to have been obtained by a Kempe change. Two colourings of G are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. A conjecture of Mohar (2007) asserts that, for k ≥ 3 , all k -colourings of a k -regular graph that is not complete are Kempe equivalent. It was later shown that all 3-colourings of a cubic graph that is neither K 4 nor the triangular prism are Kempe equivalent. In this paper, we prove that the conjecture holds for each k ≥ 4. We also report the implications of this result on the validity of the Wang–Swendsen–Kotecký algorithm for the antiferromagnetic Potts model at zero-temperature. [ABSTRACT FROM AUTHOR]