A note on orientation and chromatic number of graphs

DOI10.1007/S10878-016-0094-9MaRDI QIDQ2410109zbMATH OpenOpenAlexFDO

Authors Manouchehr Zaker

Publication date 17 October 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-016-0094-9

zbMATH Keywords

acyclic orientationchromatic numberdegenerate subgraphgraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Review text

Let \(G\) be a simple and finite graph, and let \(D\) be an orientation of \(G\). If \(D\) has a directed path of order \(k\), then define \(\Delta_k(D)\) to be the maximum value \(t\) for which a directed path \(v_1\dots v_k\) in \(D\) satisfies that the outdegree of \(v_k\) in \(D\) is \(t\); otherwise, define \(\Delta_k(D)\) to be zero. The author of this paper mainly shows first that if \(D\) is an orientation of \(G\) such that the number of Eulerian subgraphs of \(D\) of an even size is not the same as that of an odd size, then \(\chi(G)\leq \Delta_k(D)+k\). Secondly, the author shows that for any orientation \(D\) of \(G\), \(\chi(G)\leq 2\Delta_k(D)+k\). In addition, the author also provides a relation between \(\Delta_k(D)\) and vertex partitions of a graph into degenerate subgraphs.

Recommendations

• Oriented graph coloring
• Colorings and orientations of graphs
• The chromatic number of oriented graphs
• Circular colouring and orientation of graphs
• Acyclic and oriented chromatic numbers of graphs

Cites work

• Acyclic orientations of a graph and the chromatic and independence numbers
• Acyclic orientations with path constraints
• Colorings and orientations of graphs
• Decomposing a planar graph of girth 5 into an independent set and a forest
• Generating all the acyclic orientations of an undirected graph
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3205929 (Why is no real title available?)
• New bounds for the chromatic number of graphs
• Nombre chromatique et plus longs chemins d'un graphe
• Partition the vertices of a graph into one independent set and one acyclic set
• Solutions of irreflexive relations

Cited in

(10)

• On the oriented chromatic number of grids
• A note on the orientation covering number
• Chromatic number and orientations of graphs and signed graphs
• The oriented chromatic number of Halin graphs
• On the oriented chromatic number of graphs with given excess
• Complete oriented colourings and the oriented achromatic number
• Degrees in oriented hypergraphs and Ramsey p-chromatic number
• Sparse graphs are near-bipartite
• A note on orientations of mixed graphs
• Proper orientations and proper chromatic number

This page was built for publication: A note on orientation and chromatic number of graphs

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