Graphs of large linear size are antimagic

Given a graph \(G=(V,E)\) and a colouring \(f:E\mapsto \mathbb N\), the induced colour of a vertex \(v\) is the sum of the colours at the edges incident with \(v\). If all the induced colours of vertices of \(G\) are distinct, the colouring is called antimagic. If \(G\) has a bijective antimagic col...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2014-09
Main Author: Eccles, Tom
Format: Article
Language:English
Subjects:
Apexes
Coloring
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a graph \(G=(V,E)\) and a colouring \(f:E\mapsto \mathbb N\), the induced colour of a vertex \(v\) is the sum of the colours at the edges incident with \(v\). If all the induced colours of vertices of \(G\) are distinct, the colouring is called antimagic. If \(G\) has a bijective antimagic colouring \(f:E\mapsto \{1,\dots,|E|\}\), the graph \(G\) is called antimagic. A conjecture of Hartsfield and Ringel states that all connected graphs other than \(K_2\) are antimagic. Alon, Kaplan, Lev, Roddity and Yuster proved this conjecture for graphs with minimum degree at least \(c \log |V|\) for some constant \(c\); we improve on this result, proving the conjecture for graphs with average degree at least some constant \(d_0\).
ISSN:2331-8422