Reference : Competition Numbers, Quasi-Line Graphs and Holes
 Document type : Scientific journals : Article Discipline(s) : Physical, chemical, mathematical & earth Sciences : Mathematics To cite this reference: http://hdl.handle.net/10993/11471
 Title : Competition Numbers, Quasi-Line Graphs and Holes Language : English Author, co-author : McKay, Brendan [Australian National University > Research School of Computer Science] Schweitzer, Pascal [ETH Zürich > Forschungsinstitut für Mathematik] Schweitzer, Patrick [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >] Publication date : In press Journal title : SIAM Journal on Discrete Mathematics Publisher : Society for Industrial & Applied Mathematics Peer reviewed : Yes (verified by ORBilu) Audience : International ISSN : 0895-4801 Keywords : [en] Competition Number ; Competition Graph ; Quasi-Line Graph ; Number of Holes Abstract : [en] The competition graph of an acyclic directed graph D is the undirected graph on the same vertex set as D in which two distinct vertices are adjacent if they have a common out-neighbor in D. The competition number of an undirected graph G is the least number of isolated vertices that have to be added to G to make it the competition graph of an acyclic directed graph. We resolve two conjectures concerning competition graphs. First we prove a conjecture of Opsut by showing that the competition number of every quasi-line graph is at most 2. Recall that a quasi-line graph, also called a locally co-bipartite graph, is a graph for which the neighborhood of every vertex can be partitioned into at most two cliques. To prove this conjecture we devise an alternative characterization of quasi-line graphs to the one by Chudnovsky and Seymour. Second, we prove a conjecture of Kim by showing that the competition number of any graph is at most one greater than the number of holes in the graph. Our methods also allow us to prove a strengthened form of this conjecture recently proposed by Kim, Lee, Park and Sano, showing that the competition number of any graph is at most one greater than the dimension of the subspace of the cycle space spanned by the holes. Permalink : http://hdl.handle.net/10993/11471 Other URL : http://arxiv.org/abs/1110.2933

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
1110.2933v3.pdfAuthor preprint238.44 kBRequest a copy

All documents in ORBilu are protected by a user license.