Academic Journals Database
Disseminating quality controlled scientific knowledge

Graph Theory. 2. Vertex Descriptors and Graph Coloring

Author(s): Lorentz JÄNTSCHI

Journal: Leonardo Electronic Journal of Practices and Technologies
ISSN 1583-1078

Volume: 1;
Issue: 1;
Start page: 37;
Date: 2002;
Original page

Keywords: Graph theory | Vertex descriptors | Matrix based descriptors | Invariants | Graph coloring | Graph partitioning

This original work presents the construction of a set of ten sequence matrices and their applications for ordering vertices in graphs. For every sequence matrix three ordering criteria are applied: lexicographic ordering, based on strings of numbers, corresponding to every vertex, extracted as rows from sequence matrices; ordering by the sum of path lengths from a given vertex; and ordering by the sum of paths, starting from a given vertex. We also examine a graph that has different orderings for the above criteria. We then proceed to demonstrate that every criterion induced its own partition of graph vertex. We propose the following theoretical result: both LAVS and LVDS criteria generate identical partitioning of vertices in any graph. Finally, a coloring of graph vertices according to introduced ordering criteria was proposed.