Competition numbers of planar graphs

2016/02/15 by Jihoon Choi, Choi, Jihoon, Soogang Eoh +3
Mathematics · #05C20 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C20 #msc:05C75

paper · pdf · doi:10.48550/arxiv.1602.04623

15 pages, 3 figures

arxiv created 2018/10/11 · arxiv updated 2018/10/12

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) ≥ θ_e(G)-|V(G)|+\widetildek(G) where θ_e(G), k(G), and \widetildek(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.

Related

• The competition number of a graph in which any two holes share at most one edge
• Competition Numbers, Quasi-Line Graphs and Holes
• Cover numbers by certain graph families
• Edge Clique Covers in Graphs with Independence Number Two: a Special Case
• The Gamma-Theta Conjecture holds for planar graphs