Oriented cliques and colorings of graphs with low maximum degree

DOI10.1016/j.disc.2020.111829zbMath1435.05073OpenAlexW3004085525MaRDI QIDQ2305935

Alexandre Pinlou, Pascal Ochem, Andrzej Szepietowski, Janusz Dybizbański

Publication date: 20 March 2020

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

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-02938614/file/dops19.pdf

zbMATH Keywords

homomorphismoriented graphbounded degree graphoriented clique

Mathematics Subject Classification ID

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

Related Items

Coloring graphs in oriented coloring of cubic graphs ⋮ Equitable oriented coloring ⋮ On the pushable chromatic number of various types of grids ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ Colourings of oriented connected cubic graphs

Uses Software

• GENREG

Cites Work

• Unnamed Item
• Homomorphisms and colourings of oriented graphs: an updated survey
• Oriented colorings of triangle-free planar graphs
• Oriented vertex and arc colorings of outerplanar graphs
• Oriented colorings of 2-outerplanar graphs
• Oriented colorings of partial 2-trees
• An oriented coloring of planar graphs with girth at least five
• Untere Schranken für die Reichweiten von Extremalbasen fester Ordnung
• On the maximum average degree and the oriented chromatic number of a graph
• Good and semi-strong colorings of oriented planar graphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Oriented colourings of graphs with maximum degree three and four
• The oriented chromatic number of Halin graphs
• An oriented 7-colouring of planar graphs with girth at least 7
• An oriented colouring of planar graphs with girth at least 4
• Acyclic and oriented chromatic numbers of graphs
• Fast generation of regular graphs and construction of cages
• The chromatic number of oriented graphs
• Analogues of cliques for oriented coloring
• Homomorphism bounds for oriented planar graphs
• Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs
• Oriented graph coloring