Hadwiger's Conjecture for 3-Arc Graphs

  • David R Wood
  • Guangjun Xu
  • Sanming Zhou
Keywords: Hadwiger's conjecture, Graph colouring, Graph minor, $3$-Arc graph

Abstract

The 3-arc graph of a digraph $D$ is defined to have vertices the arcs of $D$ such that two arcs $uv, xy$ are adjacent if and only if $uv$ and $xy$ are distinct arcs of $D$ with $v\ne x$, $y\ne u$ and $u,x$ adjacent. We prove Hadwiger's conjecture for 3-arc graphs.

Published
2016-11-10
Article Number
P4.21