Source author record

Guillaume Aubian

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

(P6, triangle)-free digraphs have bounded dichromatic number

The dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced directed path on six vertices and no triangle have bounded dichromatic number. This is one (small) step towards the general conjecture asserting that for every oriented tree T and every integer k, any oriented graph that does not contain an induced copy of T nor a clique of size k has dichromatic number at most some function of k and T.

preprint2022arXiv

Vizing's and Shannon's Theorems for defective edge colouring

We call a multigraph $(k,d)$ -edge colourable if its edge set can be partitioned into $k$ subgraphs of maximum degree at most $d$ and denote as $χ'_{d}(G)$ the minimum $k$ such that $G$ is $(k,d)$ -edge colourable. We prove that for every integer $d$ , every multigraph $G$ with maximum degree $Δ$ is $(\lceil \fracΔ{d} \rceil, d)$ -edge colourable if $d$ is even and $(\lceil \frac{3Δ- 1}{3d - 1} \rceil, d)$ -edge colourable if $d$ is odd and these bounds are tight. We also prove that for every simple graph $G$ , $χ'_{d}(G) \in \{ \lceil \fracΔ{d} \rceil, \lceil \frac{Δ+1}{d} \rceil \}$ and characterize the values of $d$ and $Δ$ for which it is NP-complete to compute $χ'_d(G)$ . These results generalize several classic results on the chromatic index of a graph by Shannon, Vizing, Holyer, Leven and Galil.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.