Premium
On fans in multigraphs
Author(s) -
Cariolaro David
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20135
Subject(s) - multigraph , combinatorics , digraph , lemma (botany) , mathematics , vertex (graph theory) , mathematical proof , edge coloring , graph , directed graph , adjacency list , strongly connected component , discrete mathematics , line graph , botany , graph power , geometry , poaceae , biology
We introduce a unifying framework for studying edge‐coloring problems on multigraphs. This is defined in terms of a rooted directed multigraph $\cal F$ , which is naturally associated to the set of fans based at a given vertex u in a multigraph G . We call $\cal F$ the “Fan Digraph.” We show that fans in G based at u are in one‐to‐one correspondence with directed trails in $\cal F$ starting at the root of $\cal F$ . We state and prove a central theorem about the fan digraph, which embodies many edge‐coloring results and expresses them at a higher level of abstraction. Using this result, we derive short proofs of classical theorems. We conclude with a new, generalized version of Vizing's Adjacency Lemma for multigraphs, which is stronger than all those known to the author. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 301–318, 2006