Iterated arc graphs.

DOI10.14712/1213-7243.2015.260MaRDI QIDQ4683356zbMATH OpenOpenAlexWikidataFDO

Authors Danny Rorabaugh, Claude Tardif, David Wehlau, Imed Zaguia

Publication date 20 September 2018

Published in Commentationes Mathematicae Universitatis Carolinae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01259, http://hdl.handle.net/10338.dmlcz/147397

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic numberDedekind numberfree distributive latticearc graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Combinatorics of partially ordered sets (06A07)

Abstract: The arc graph $delta(G)$ of a digraph $G$ is the digraph with the set of arcs of $G$ as vertex-set, where the arcs of $delta(G)$ join consecutive arcs of $G$. In 1981, Poljak and R"{o}dl characterised the chromatic number of $delta(G)$ in terms of the chromatic number of $G$ when $G$ is symmetric (i.e., undirected). In contrast, directed graphs with equal chromatic numbers can have arc graphs with distinct chromatic numbers. Even though the arc graph of a symmetric graph is not symmetric, we show that the chromatic number of the iterated arc graph $delt{a}^k(G)$ still only depends on the chromatic number of $G$ when $G$ is symmetric.

Recommendations

• Distinguishing arc-colourings of symmetric digraphs
• Proper distinguishing arc-colourings of symmetric digraphs
• ON THE DICHROMATIC INDEX OF A DIGRAPH
• scientific article; zbMATH DE number 37867
• On the maximum arc-chromatic number of digraphs with bounded outdegrees or indegrees

Cites work

• scientific article; zbMATH DE number 37867 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• Arc colorings of digraphs
• Digraph functors which admit both left and right adjoints
• On the arc-chromatic number of a digraph
• The level polynomials of the free distributive lattices

Cited in

(2)

• On inverse powers of graphs and topological implications of Hedetniemi's conjecture
• Archimedean graph designs. II.

This page was built for publication: Iterated arc graphs.

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