Oriented colourings of graphs with maximum degree three and four

DOI10.1016/J.DISC.2018.10.008MaRDI QIDQ1727768zbMATH OpenOpenAlexFDO

Authors Christopher Duffy, Gary MacGillivray, Éric Sopena

Publication date 20 February 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.05510

zbMATH Keywords

oriented graph colouringoriented graph homomorphism

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Abstract: We show that any orientation of a graph with maximum degree three has an oriented 9-colouring, and that any orientation of a graph with maximum degree four has an oriented 69-colouring. These results improve the best known upper bounds of 11 and 80, respectively.

Recommendations

• An oriented colouring of planar graphs with girth at least 4
• Orientations and 3-colourings of graphs.
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• Oriented cliques and colorings of graphs with low maximum degree
• Colorings and orientations of graphs
• Colourings of oriented connected cubic graphs
• Coloring graphs in oriented coloring of cubic graphs
• Orientable edge colorings of graphs
• Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs
• scientific article; zbMATH DE number 21752

Cites work

• A Constructive Solution to a Tournament Problem
• Acyclic and oriented chromatic numbers of graphs
• Acyclic colorings of planar graphs
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Analogues of cliques for oriented coloring
• Good and semi-strong colorings of oriented planar graphs
• Homomorphisms and colourings of oriented graphs: an updated survey
• On an adjacency property of almost all tournaments
• On the oriented chromatic number of dense graphs
• On the oriented chromatic number of grids
• Oriented vertex and arc colorings of outerplanar graphs
• Paley graphs satisfy all first-order adjacency axioms
• The chromatic number of oriented graphs
• The oriented chromatic number of Halin graphs
• The search for N-e.c. Graphs

Cited in

(11)

• Orientations and 3-colourings of graphs.
• Chromatic polynomials of oriented graphs
• Equitable oriented coloring
• Pushable chromatic number of graphs with degree constraints
• Coloring graphs in oriented coloring of cubic graphs
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• Maximal colourings for graphs
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• An oriented colouring of planar graphs with girth at least 4
• Colourings of oriented connected cubic graphs
• Oriented cliques and colorings of graphs with low maximum degree

This page was built for publication: Oriented colourings of graphs with maximum degree three and four

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1727768)