Colouring complete multipartite and Kneser-type digraphs

EUROCOMB’23

Abstract
The dichromatic number of a digraph $D$ is the smallest $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs, and the dichromatic number of an undirected graph is the maximum dichromatic number over all its orientations. We present bounds for the dichromatic number of Kneser graphs and Borsuk graphs, and for the list dichromatic number of certain classes of Kneser graphs and complete multipartite graphs. The bounds presented are sharp up to a constant factor. Additionally, we give a directed analogue of Sabidussi‘s theorem on the chromatic number of graph products.

Pages:
545–551
References

N. Alon. Choice Numbers of Graphs: a Probabilistic Approach. Combinatorics, Probability and Computing, 1(2):107-114, 1992.
https://doi.org/10.1017/S0963548300000122

J. Bensmail, A. Harutyunyan, and N. K. Le. List coloring digraphs. Journal of Graph Theory, 87(4):492-508, 2018.
https://doi.org/10.1002/jgt.22170

D. Bokal, G. Fijavz, M. Juvan, P. Kayll, and B. Mohar. The circular chromatic number of a digraph. Journal of Graph Theory, 46(3):227-240, 2004.
https://doi.org/10.1002/jgt.20003

V. Bulankina and A. Kupavskii. Choice number of Kneser graphs. Discrete Mathematics, 345(11),
https://doi.org/10.1016/j.disc.2022.113097

2022.

P. Erdős. Problems and results in number theory and graph theory. In Proceedings of the 9th Manitoba Conference on Numerical Mathematics and Computing, pages 3-21, 1979.

P. Erdős, A. L. Rubin, and H. Taylor. Choosability in graphs. In Proceedings of the West Coast

Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium 26, pages

125-157, 1980.

J. E. Greene. A New Short Proof of Kneser's Conjecture. The American Mathematical Monthly,

109(10):918-920, 2002.

A. Harutyunyan and B. Mohar. Gallai's Theorem for List Coloring of Digraphs. SIAM Journal on

Discrete Mathematics, 25(1):170-180, 2011.
https://doi.org/10.1137/100803870

A. Harutyunyan and B. Mohar. Strengthened Brooks' Theorem for Digraphs of Girth at least Three.

Electr. J. Comb., 18, 10 2011.

A. Harutyunyan and B. Mohar. Two results on the digraph chromatic number. Discrete Mathematics, 312(10):1823-1826, 2012.
https://doi.org/10.1016/j.disc.2012.01.028

M. Kneser. Aufgabe 360. Jahresbericht der Deutschen Mathematiker-Vereinigung, 58(27):107-116,

1955.

L. Lovász. Kneser's Conjecture, Chromatic Number, and Homotopy. Journal of Combinatorial Theory, Series A, 25(3):319-324, 1978.
https://doi.org/10.1016/0097-3165(78)90022-5

J. Matoušek, A. Björner, and G. M. Ziegler. Using the Borsuk-Ulam Theorem. Berlin: Springer, 2003.

B. Mohar. Circular colorings of edge-weighted graphs. Journal of Graph Theory, 43:107-116, 2003.
https://doi.org/10.1002/jgt.10106

B. Mohar and H. Wu. Dichromatic number and fractional chromatic number. Forum of Mathematics, Sigma, 4, 2016.
https://doi.org/10.1017/fms.2016.28

M. Molloy and B. Reed. Graph Colouring and the Probabilistic Method. Springer, 2002.
https://doi.org/10.1007/978-3-642-04016-0

V. Neumann-Lara. The Dichromatic Number of a Digraph. Journal of Combinatorial Theory, 33:265-270, 1982.
https://doi.org/10.1016/0095-8956(82)90046-6

G. Sabidussi. Graphs with Given Group and Given Graph-Theoretical Properties. Canadian Journal

of Mathematics, 9:515-525, 1957.
https://doi.org/10.4153/CJM-1957-060-7

V. G. Vizing. Vertex colorings with given colors (in Russian). Metody Diskret. Analiz., 29:3-10, 1976.

G. M. Ziegler. "Aufgabe 360: The Kneser Conjecture", pages 743-749. Springer International Publishing, 2021.
https://doi.org/10.1007/978-3-030-81625-4_7

Metrics

0

Views

0

PDF views