The oriented chromatic number of Halin graphs

DOI10.1016/J.IPL.2013.09.011MaRDI QIDQ2350598zbMATH OpenOpenAlexFDO

Authors Janusz Dybizbański, Andrzej Szepietowski

Publication date 25 June 2015

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial problemsgraph coloringHalin graphoriented chromatic numberoriented graph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Oriented chromatic number of an oriented graph $G$ is the minimum order of an oriented graph $H$ such that $G$ admits a homomorphism to $H$. The oriented chromatic number of an unoriented graph $G$ is the maximal chromatic number over all possible orientations of $G$. In this paper, we prove that every Halin graph has oriented chromatic number at most 8, improving a previous bound by Hosseini Dolama and Sopena, and confirming the conjecture given by Vignal.

Recommendations

• On the oriented chromatic number of Halin graphs
• The chromatic number of oriented graphs
• On the chromatic number of Halin graphs
• The simple chromatic number of oriented graphs
• A note on orientation and chromatic number of graphs
• On the oriented chromatic index of oriented graphs
• Acyclic and oriented chromatic numbers of graphs
• scientific article; zbMATH DE number 679745
• On the complete chromatic number of Halin graphs
• On the oriented chromatic number of dense graphs

Cites work

• A note on the oriented chromatic number of grids
• Acyclic and oriented chromatic numbers of graphs
• Good and semi-strong colorings of oriented planar graphs
• scientific article; zbMATH DE number 3342024 (Why is no real title available?)
• On the maximum average degree and the oriented chromatic number of a graph
• On the oriented chromatic number of graphs with given excess
• On the oriented chromatic number of grids
• On the oriented chromatic number of Halin graphs
• Oriented chromatic number of grids is greater than 7
• Oriented graph coloring
• The chromatic number of oriented graphs

Cited in

(14)

• Oriented chromatic number of Cartesian products and strong products of paths
• Oriented colourings of graphs with maximum degree three and four
• Oriented coloring on recursively defined digraphs
• Oriented chromatic number of Cartesian products \(P_m \square P_n\) and \(C_m \square P_n \)
• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• Oriented cliques and colorings of graphs with low maximum degree
• Chromatic polynomials of oriented graphs
• On the oriented chromatic number of graphs with given excess
• Homomorphisms and colourings of oriented graphs: an updated survey
• Group chromatic number of Halin graphs
• The oriented chromatic number of the hexagonal grid is 6
• On the oriented chromatic number of Halin graphs
• The 2-dipath chromatic number of Halin graphs

This page was built for publication: The oriented chromatic number of Halin graphs

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