Cover Image

Oriented trees in $O(k \sqrt{k})$-chromatic digraphs, a subquadratic bound for Burr's conjecture

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bessy, Stéphane, Gonçalves, Daniel, Reinald, Amadeus
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Discrete Mathematics 05C20
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of $P_4$
by: Cook, Linda, et al.
Published: (2022)

Inversion diameter and 2-edge-colored homomorphisms
by: Arana, Carmen, et al.
Published: (2026)

Plane Strong Connectivity Augmentation
by: Bessy, Stéphane, et al.
Published: (2025)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

On the Small Quasi-kernel conjecture
by: Erdős, Péter L., et al.
Published: (2023)

Asymptotics of relaxed $k$-ary trees
by: Dastidar, Manosij Ghosh, et al.
Published: (2024)

Brooks-type colourings of digraphs in linear time
by: Gonçalves, Daniel, et al.
Published: (2024)

Isolation of regular graphs and $k$-chromatic graphs
by: Borg, Peter
Published: (2023)

A characterization of interval nest digraphs
by: Alcantar, Ayelén, et al.
Published: (2026)

Isolation of regular graphs, stars and $k$-chromatic graphs
by: Borg, Peter
Published: (2023)

$k$-path graphs: experiments and conjectures about algebraic connectivity and $α$-index
by: de Paula, Rafael L., et al.
Published: (2025)

Symmetric Rule-Based Achlioptas Processes for Random $k$-SAT
by: Chatterjee, Arnab
Published: (2025)

Aharoni's rainbow cycle conjecture holds up to an additive constant
by: Hompe, Patrick, et al.
Published: (2022)

Constant congestion brambles in directed graphs
by: Masařík, Tomáš, et al.
Published: (2021)

Circular chromatic index of small graphs
by: Mazák, Ján, et al.
Published: (2026)

On Oriented Diameter of Power Graphs
by: Benson, Deepu, et al.
Published: (2024)

Burling graphs in graphs with large chromatic number
by: Abrishami, Tara, et al.
Published: (2025)

On acyclic b-chromatic number of cubic graphs
by: Anholcer, Marcin, et al.
Published: (2025)

Feedback vertex sets of planar digraphs with fixed digirth
by: Dreyer, Simon, et al.
Published: (2026)

The $χ$-binding function of $d$-directional segment graphs
by: Duraj, Lech, et al.
Published: (2023)

Homomorphically Full Oriented Graphs
by: Bellitto, Thomas, et al.
Published: (2022)

Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order
by: Aboulker, Pierre, et al.
Published: (2024)

Cycles of weight divisible by $k$
by: Diwan, Ajit A.
Published: (2024)

Finite Vertex-colored Ultrahomogeneous Oriented Graphs
by: Heinrich, Irene, et al.
Published: (2024)

$\mathcal{O}(VE)$ time algorithms for the Grundy (First-Fit) chromatic number of block graphs and graphs with sufficiently large girth
by: Zaker, Manouchehr
Published: (2024)

Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$
by: Picasarri-Arrieta, Lucas, et al.
Published: (2023)

Automorphism groups of graphs of bounded Hadwiger number
by: Grohe, Martin, et al.
Published: (2020)

Computing the permanental polynomial of $4k$-intercyclic bipartite graphs
by: Bapat, Ravindra B., et al.
Published: (2024)

Simultaneous separation in bounded degree trees
by: Snir, Sagi, et al.
Published: (2026)

The strong vertex span of trees
by: Grašič, Mateja, et al.
Published: (2024)

An improved upper bound for the domination number of a graph
by: Arumugam, Subramanian, et al.
Published: (2024)

Proof of a conjecture on isolation of graphs dominated by a vertex
by: Borg, Peter
Published: (2024)

Proof of a conjecture on isolation of graphs with a universal vertex
by: Borg, Peter, et al.
Published: (2025)

On the minimum number of inversions to make a digraph $k$-(arc-)strong
by: Duron, Julien, et al.
Published: (2023)

Branching $k$-path vertex cover of forests
by: Makarov, Mikhail
Published: (2026)

Bounding the chromatic number of dense digraphs by arc neighborhoods
by: Klingelhoefer, Felix, et al.
Published: (2023)

A Graph-Theoretic Model for a Generic Three-Jug Puzzle
by: Hegde, Suresh Manjanath, et al.
Published: (2023)

On the concentration of the chromatic number of random graphs
by: Surya, Erlang, et al.
Published: (2022)

Structure of $k$-Matching-Planar Graphs
by: Hendrey, Kevin, et al.
Published: (2025)

The decompressed tree size of $k$-ary chains
by: Wallner, Michael
Published: (2026)