Chordal graphs are fully orientable.

zbMATH Open1363.05098arXiv1202.5718MaRDI QIDQ2823219FDOQ2823219

Authors: Hsin-Hao Lai, Ko-Wei Lih 

Publication date: 6 October 2016

Published in: Ars Combinatoria (Search for Journal in Brave)

Abstract: Suppose that D is an acyclic orientation of a graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let m and M denote the minimum and the maximum of the number of dependent arcs over all acyclic orientations of G. We call G fully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying m <= d <= M. A graph G is called chordal if every cycle in G of length at least four has a chord. We show that all chordal graphs are fully orientable.

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

Recommendations

• Full orientability of graphs
• Full orientability of graphs with at most one dependent arc
• Full orientability of the square of a cycle.
• On preserving full orientability of graphs
• On fully orientability of 2-degenerate graphs

zbMATH Keywords

simplicial vertexchordal graphacyclic orientationfull orientability graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Cited In (3)

• Full orientability of graphs with at most one dependent arc
• Title not available (Why is that?)
• On cyclically orientable graphs

This page was built for publication: Chordal graphs are fully orientable.

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