BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that for every n, there is a graph G with χ(G)≥n and ω(G)≤3 such that every induced subgraph H of G with ω(H)≤2 satisfies χ(H)≤4. This disproves a well-known conjecture. Our construction is a digraph with bounded clique number, large dichromatic number, and no induced directed cycles of odd length at least 5.
We prove that every triangle-free 4-critical graph G satisfies e(G)≥35v(G)+2. This result gives a unified proof that triangle-free planar graphs are 3-colourable, and that graphs of girth at least five which embed in either the projective plane, torus, or Klein Bottle are 3-colourable, which are results of Grötzsch, Thomassen, and Thomas and Walls. Our result is nearly best possible, as Davies has constructed triangle-free 4-critical graphs G such that e(G)=35v(G)+4. To prove this result, we prove a more general result characterizing sparse 4-critical graphs with few vertex-disjoint triangles.
Given a graph G, the k-mixing problem asks: Can one obtain all k-colourings of G, starting from one k-colouring f, by changing the colour of only one vertex at a time, while at each step maintaining a k-colouring? More generally, for a graph H, the H-mixing problem asks: Can one obtain all homomorphisms G→H, starting from one homomorphism f, by changing the image of only one vertex at a time, while at each step maintaining a homomorphism G→H? This paper focuses on a generalization of k-colourings, namely (p,q)-circular colourings. We show that when 2<qp<4, a graph G is (p,q)-mixing if and only if for any (p,q)-colouring f of G, and any cycle C of G, the wind of the cycle under the colouring equals a particular value (which intuitively corresponds to having no wind). As a consequence we show that (p,q)-mixing is closed under a restricted homomorphism called a fold. Using this, we deduce that (2k+1,k)-mixing is co-NP-complete for all k∈N, and by similar ideas we show that if the circular chromatic number of a connected graph G is k2k+1, then G folds to C2k+1. We use the characterization to settle a conjecture of Brewster and Noel, specifically that the circular mixing number of bipartite graphs is 2. Lastly, we give a polynomial time algorithm for (p,q)-mixing in planar graphs when 3≤qp<4.
The Strong Nine Dragon Tree Conjecture asserts that for any integers k and d any graph with fractional arboricity at most k+d+k+1d decomposes into k+1 forests, such that for at least one of the forests, every connected component contains at most d edges. We prove this conjecture when d≤k+1. We also prove an approximate version of this conjecture, that is, we prove that for any positive integers k and d, any graph with fractional arboricity at most k+d+k+1d decomposes into k+1 forests, such that one for at least one of the forests, every connected component contains at most d+k+1d(k(2⌈k+1d+2⌉)⌈k+1d+2)⌉−k) edges.
Kostochka and Yancey proved that every 4-critical graph G has e(G)≥35v(G)−2, and that equality holds if and only if G is 4-Ore. We show that a question of Postle and Smith-Roberge implies that every 4-critical graph with no (7,2)-circular-colouring has e(G)≥1527v(G)−20. We prove that every 4-critical graph with no (7,2)-colouring has e(G)≥1017v(G) unless G is isomorphic to K4 or the wheel on six vertices. We also show that if the Gallai Tree of a 4-critical graph with no (7,2)-colouring has every component isomorphic to either an odd cycle, a claw, or a path. In the case that the Gallai Tree contains an odd cycle component, then G is isomorphic to an odd wheel. In general, we show a k-critical graph with no (2k−1,2)-colouring that contains a clique of size k−1 in it's Gallai Tree is isomorphic to Kk.
We prove that for any positive integers k and d, if a graph G has maximum average degree at most 2k+d+k+12d, then G decomposes into k+1 pseudoforests C1,…,Ck+1 such that there is an i such that for every connected component C of Ci, we have that e(C)≤d.
The "reconfiguration problem" for circular colourings asks, given two (p,q)-colourings f and g of a graph G, is it possible to transform f into g by changing the colour of one vertex at a time such that every intermediate mapping is a (p,q)-colouring? We show that this problem can be solved in polynomial time for 2≤p/q<4 and is PSPACE-complete for p/q≥4. This generalizes a known dichotomy theorem for reconfiguring classical graph colourings.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.