Search

A proper total weighting of a graph G is a mapping ϕ which assigns to each vertex and each edge of G a real number as its weight so that for any edge u v of G , ∑ e ∈ E ( v ) ϕ ( e ) + ϕ ( v ) ≠ ∑ e ∈ E ( u ) ϕ ( e ) + ϕ ( u ) . A ( k , k ′ ) -list assignment of G is a mapping L which assigns to each vertex v a set L ( v ) of k permissible weights and to each edge e a set L ( e ) of k ′ permissible weights. An L -total weighting is a total weighting ϕ with ϕ ( z ) ∈ L ( z ) for each z ∈ V ( G ) ∪ E ( G ) . A graph G is called ( k , k ′ ) -choosable if for every ( k , k ′ ) -list assignment L of G , there exists a proper L -total weighting. It was proved in Tang and Zhu (2017) that if p ∈ { 5 , 7 , 11 } , a graph G without isolated edges and with mad ( G ) ≤ p − 1 is ( 1 , p ) -choosable. In this paper, we strengthen this result by showing that for any prime p , a graph G without isolated edges and with mad ( G ) ≤ p − 1 is ( 1 , p ) -choosable. [ABSTRACT FROM AUTHOR]

A twisted hypercube of dimension k is created from two twisted hypercubes of dimension k − 1 by adding a matching joining their vertex sets, with the twisted hypercube of dimension 0 consisting of one vertex and no edges. We generate random twisted hypercube by generating the matchings randomly at each step. We show that, asymptotically almost surely, joining any two vertices in a random twisted hypercube of dimension k there are k internally disjoint paths of length at most k lg k + O k lg 2 k . Since the graph is k -regular with 2 k vertices, the number of paths is optimal and the length is asymptotically optimal. [ABSTRACT FROM AUTHOR]

For a loopless multigraph G , the fractional arboricity Arb ( G ) is the maximum of | E ( H ) | | V ( H ) | − 1 over all subgraphs H with at least two vertices. Generalizing the Nash-Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if Arb ( G ) ≤ k + d k + d + 1 , then G decomposes into k + 1 forests with one having maximum degree at most d . The conjecture was previously proved for d = k + 1 and for k = 1 when d ≤ 6 . We prove it for all d when k ≤ 2 , except for ( k , d ) = ( 2 , 1 ) . [ABSTRACT FROM AUTHOR]

A graph [ABSTRACT FROM AUTHOR]

Assume G is a graph and S is a set of permutations of positive integers. An S -labelling of G is a pair (D , σ) , where D is an orientation of G and σ : E (D) → S is a mapping which assigns to each arc e = (u , v) of D a permutation σ e ∈ S. A proper k -colouring of (D , σ) is a mapping f : V (G) → [ k ] = { 1 , 2 ,... , k } such that σ e (f (x)) ≠ f (y) for each arc e = (x , y). We say S is non-trivial if for every positive integer i , there is a permutation π ∈ S such that π (i) = i , and S is transitive if for every pair (i , j) of positive integers, there is a permutation π ∈ S such that π (i) = j or π (j) = i. The S -chromatic number of a graph G is the minimum integer k such that any S -labelling (D , σ) of G has a proper k -colouring. This paper constructs, for any non-trivial set S of permutations of integers, for any integers k , g , a graph of girth at least g and S -chromatic number greater than k. We further prove that if S is a non-trivial set of permutations of positive integers, and 2 ≤ k ′ ≤ k and g are positive integers, then the following two statements are equivalent: (1) there exists a graph of girth at least g , of chromatic number k ′ and S -chromatic number greater than k , (2) for any k ′ -subset I of [ k ] , there exist a , b ∈ I and π ∈ S such that a ≠ b and either π (a) = b or π (b) = a. As a consequence, there is a bipartite graph of arbitrary large girth and arbitrary large S -chromatic number if and only if S is transitive. In particular, there is a bipartite graph G of arbitrary large girth and arbitrary large group chromatic number. [ABSTRACT FROM AUTHOR]

Let ch ( G ) denote the choice number of a graph G (also called “list chromatic number” or “choosability” of G ). Noel, Reed, and Wu proved the conjecture of Ohba that ch ( G ) = χ ( G ) when | V ( G ) | ≤ 2 χ ( G ) + 1 . We extend this to a general upper bound: ch ( G ) ≤ max { χ ( G ) , ⌈ ( | V ( G ) | + χ ( G ) − 1 ) / 3 ⌉ } . Our result is sharp for | V ( G ) | ≤ 3 χ ( G ) using Ohba’s examples, and it improves the best-known upper bound for ch ( K 4 , … , 4 ) . [ABSTRACT FROM AUTHOR]

Abstract: Suppose that is a graph and that is a subgraph of . Let be a mapping that assigns to each vertex of a set of positive integers. We say that is backbone -colourable if there is a proper vertex colouring of such that for all , and for every edge in . We say that is backbone -choosable if is backbone -colourable for any list assignment with for all . The backbone choice number of , denoted by , is the minimum such that is backbone -choosable. The concept of a backbone choice number is a generalization of both the choice number and the -choice number. Precisely, if , then , where is the choice number of ; if , then is the same as the -choice number of . In this article, we first show that, if , then is -colourable, unless and each block of is a complete graph or an odd cycle. This generalizes a result of Erdős, Rubin, and Taylor on degree-choosable graphs. Second, we prove that , where is the maximum average degree of a graph . Finally, we establish various upper bounds on in terms of . In particular, we prove that, for a -choosable graph , if every component of is unicyclic; if is a matching; and if is a disjoint union of paths with length at most 2. [Copyright &y& Elsevier]

For a loopless multigraph G, the fractional arboricity Arb( G) is the maximum of [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the strong game colouring number of directed graphs. It is proved that every oriented partial 2-tree has strong game colouring number at most 7 and every oriented planar graph has strong game colouring number at most 15. [Copyright &y& Elsevier]

Abstract: Suppose is a graph and is a colouring of its edges (not necessarily proper) that uses the colour set . In an adapted colouring game, Alice and Bob alternately colour uncoloured vertices of with colours from . A partial colouring of the vertices of is legal if there is no edge such that . In the process of the game, each partial colouring must be legal. If eventually all the vertices of are coloured, then Alice wins the game. Otherwise, Bob wins the game. The adapted game chromatic number of a graph , denoted by , is the minimum number of colours needed to ensure that for any edge colouring of , Alice has a winning strategy for the game. This paper studies the adapted game chromatic number of various classes of graphs. We prove that the maximum adapted game chromatic number of trees is , the maximum adapted game chromatic number of outerplanar graphs is , the adapted game chromatic number of partial -trees is at most , and the adapted game chromatic number of planar graphs is at most . [Copyright &y& Elsevier]

Abstract: The fractional arboricity of a graph G is the maximum of the ratio over all the induced subgraphs of G. In this paper, we propose a conjecture which says that every graph G with decomposes into forests, and one of the forests has maximum degree at most d. We prove two special cases of this conjecture: if G is a graph with fractional arboricity at most , then G decomposes into a forest and a matching. If G is a graph with fractional arboricity at most , then G decomposes into a forest and a linear forest. In particular, every planar graph of girth at least 8 decomposes into a forest and a matching, and every planar graph of girth at least 6 decomposes into a forest and a linear forest. This improves earlier results concerning decomposition of planar graphs, and the girth condition is sharp, as there are planar graphs of girth 7 which do not decompose into a forest and a matching, and there are planar graphs of girth 5 which do not decompose into a forest and a linear forest. The bound in the conjecture above is sharp: We shall show that for any , there is a graph G with , and yet G cannot be decomposed into k forests plus a graph of maximum degree at most d. On the other hand, we show that for any positive integer k and real number , every graph G with decomposes into k forests plus a graph of maximum degree at most . [Copyright &y& Elsevier]

Abstract: Let be a nonnegative integer, and let . We prove that every simple graph with maximum average degree less than decomposes into a forest and a subgraph with maximum degree at most (furthermore, when both subgraphs can be required to be forests). It follows that every simple graph with maximum average degree less than has game coloring number at most . [Copyright &y& Elsevier]

Abstract: A colouring of the vertices of a graph (or hypergraph) is adapted to a given colouring of the edges of if no edge has the same colour as both (or all) its vertices. The adaptable chromatic number of is the smallest integer such that each edge-colouring of by colours admits an adapted vertex-colouring of by the same colours . (The adaptable chromatic number is just one more than a previously investigated notion of chromatic capacity.) The adaptable chromatic number of a graph is smaller than or equal to the ordinary chromatic number of . While the ordinary chromatic number of all (categorical) powers of remains the same as that of , the adaptable chromatic number of may increase with . We conjecture that for all sufficiently large the adaptable chromatic number of equals the chromatic number of . When is complete, we prove this conjecture with , and offer additional evidence suggesting it may hold with . We also discuss other products and propose several open problems. [Copyright &y& Elsevier]

Abstract: We show that for each and each integer , there exists a number g such that for any graph G of maximum degree Δ and girth at least g, the circular chromatic index of G is at most . [Copyright &y& Elsevier]