Search

Brooks’ theorem implies that if a graph has Δ ≥ 3 and χ > Δ, then ω = Δ+1. Borodin and Kostochka conjectured that if Δ ≥ 9 and χ ≥ Δ, then ω ≥ Δ. We show that if Δ ≥ 13 and χ ≥ Δ, then ω ≥ Δ−3. For a graph G, let H(G) denote the subgraph of G induced by vertices of degree Δ. We also show that if χ ≥ Δ, then ω ≥ Δ or ω(H(G)) ≥ Δ − 5. [ABSTRACT FROM AUTHOR]

An antimagic labeling of a graph G with m edges is a bijection from [ABSTRACT FROM AUTHOR]

We prove that every claw-free graph G that does not contain a clique on Δ(G) ≥ 9 vertices can be Δ(G) -- 1 colored. [ABSTRACT FROM AUTHOR]

The following question was raised by Bruce Richter. Let G be a planar, 3-connected graph that is not a complete graph. Denoting by d( v) the degree of vertex v, is G L-list colorable for every list assignment L with | L( v)| = min{ d( v), 6} for all v∈ V( G)? More generally, we ask for which pairs ( r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K5-minor-free r-connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L-list colorable for every list assignment L with | L( v)| = min{ d( v), k} for all v∈ V( G)? We investigate this question by considering the components of G[ S k], where S k: = { v∈ V( G)| d( v)8 k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d( S k) in G between the components of G[ S k]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18-30, 2012 [ABSTRACT FROM AUTHOR]

The reconfiguration graph C k (G) for the k -colourings of a graph G has a vertex for each proper k -colouring of G , and two vertices of C k (G) are adjacent precisely when those k -colourings differ on a single vertex of G. Much work has focused on bounding the maximum value of diam C k (G) over all n -vertex graphs G. We consider the analogous problems for list colourings and for correspondence colourings. We conjecture that if L is a list-assignment for a graph G with | L (v) | ≥ d (v) + 2 for all v ∈ V (G) , then diam C L (G) ≤ n (G) + μ (G). We also conjecture that if (L , H) is a correspondence cover for a graph G with | L (v) | ≥ d (v) + 2 for all v ∈ V (G) , then diam C (L , H) (G) ≤ n (G) + τ (G). (Here μ (G) and τ (G) denote the matching number and vertex cover number of G.) For every graph G , we give constructions showing that both conjectures are best possible, which also hints towards an exact form of Cereceda's Conjecture for regular graphs. Our first main result proves the upper bounds (for the list and correspondence versions, respectively) diam C L (G) ≤ n (G) + 2 μ (G) and diam C (L , H) (G) ≤ n (G) + 2 τ (G). Our second main result proves that both conjectured bounds hold, whenever all v satisfy | L (v) | ≥ 2 d (v) + 1. We conclude by proving one or both conjectures for various classes of graphs such as complete bipartite graphs, subcubic graphs, cactuses, and graphs with bounded maximum average degree. The full paper can also be found at arxiv.org/abs/2204.07928. [ABSTRACT FROM AUTHOR]