Premium
Constructions of bipartite graphs from finite geometries
Author(s) -
Mellinger Keith E.,
Mubayi Dhruv
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20059
Subject(s) - mathematics , bipartite graph , combinatorics , cograph , discrete mathematics , 1 planar graph , graph , chordal graph
We construct an incidence structure using certain points and lines in finite projective spaces. The structural properties of the associated bipartite incidence graphs are analyzed. These n × n bipartite graphs provide constructions of C 6 ‐free graphs with Ω( n 4/3 edges, C 10 ‐free graphs with Ω( n 6/5 ) edges, and Θ(7,7,7)‐free graphs with Ω( n 8/7 ) edges. Each of these bounds is sharp in order of magnitude. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 1–10, 2005
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom