Competition numbers of planar graphs

Abstract

In this paper, we relate the competition number of a graph to its edge clique cover number by presenting a tight inequality $k(G)\ge {\theta }_e(G)-|V(G)|+\tilde{k}(G)$ where ${\theta }_e(G)$, $k(G)$, and $\tilde{k}(G)$ are the edge clique cover number, the competition number, and the co-competition number of a graph $G$, respectively. By utilizing this inequality and a notion of competition-effective edge clique cover, we obtain some meaningful results on competition numbers of planar graphs.

15 pages, 3 figures

References in corpus (1)

• The competition number of a graph with exactly two holes