Oriented colourings of graphs with maximum degree three and four

DOI10.1016/J.DISC.2018.10.008zbMATH Open1405.05056arXiv1812.05510OpenAlexW2904851722MaRDI QIDQ1727768FDOQ1727768

Authors: Christopher Duffy, Gary MacGillivray, Éric Sopena 

Publication date: 20 February 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (11)

• Orientations and 3-colourings of graphs.
• Equitable oriented coloring
• Chromatic polynomials of oriented graphs
• 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)