Combinatorics and Graph Theory


The Chromatic-Covering of a Graph: Ratios, Domination, Areas and Farey Sequences

Authors: Paul August Winter

The study of the chromatic number and vertex coverings of graphs has opened many avenues of research. In this paper we combine these two concepts in a ratio, to investigate the domination effect of the chromatic number, of the subgaph induced by a vertex covering of a graph G (called the cover graph of G), on the original chromatic number of G, where large number of vertices are involved. This is referred to as the chromatic-cover domination. If this chromatic-cover ratio is a function of n, the order of graphs belonging to a class of graph, then we discuss its horizontal asymptotic behavior and attach the graphs average degree to the Riemann integral of this ratio, thus associating chromatic-cover area with classes of graphs. We found that the chromatic-cover domination had a strongest effect on complete graph, while this chromatic-cover domination had zero effect on star graphs. We show that the chromatic-cover asymptote of all classes of graphs belong to the interval [0,1], and conjecture that complete graphs are the only class of graphs having chromatic-cover asymptote of 1 and that they also have the largest area . We construct a class of graphs, using known classes of graph where vertices are replaced with cliques on q vertices, thus generating sequences which converges to the chromatic-cover asymptote of known classes of graphs. We use a particular sequence to construct a Farey chromatic-cover sequence which is a subsequence of the famous Farey sequence.

Comments: 21 Pages.

Download: PDF

Submission history

[v1] 2014-09-14 08:55:20

Unique-IP document downloads: 83 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus