Graphs with maximal Rank:                          Torsten Sillke
-------------------------
Cographs are the graphs formed from a single vertex under the closure
of the operations of union and complement. (see: Corneil)

Another characterization of cographs is: Cographs do not contain
a induced P_4. (see Seinsche)

Lovasz gives the following construction of P_4 free graphs:
Graphs containing no P_4 can be obtained from K_1 by repeared doubling
of one point with or without joining the two doubles.


Let A(G) be the adjacency matrix of the graph G.

Conjecture:
  For a cograph G there is
  rg( A(G) ) = the number of different nonzero columns of A(G).

Are there other classes of graphs with this property?


References (of Cographs or P_4 free graphs):
- Corneil, et al;
  SIAM J Comput 14 (1985) 926

- L. Lovasz;
  Discrete Mathematics 2 (1972) 253-267

- D. Seinsche;
  On a Property of the Class of n-Colorable Graphs
  Journal of Combinatorial Theory B 16 (1974) 191-193
  Zbl 269.05103

References of eigenvalues and their relation to other graph properties:
- D. Cvetkovic, Doob, and Sachs;
  Spectra of Graphs
  Academic Press 1978

History:
In 1988 I tried to find counterexamples to the 
"chromatic number <= rank" problem. I generated all
graphs with rank upto 5. I could ignore graph where two
points had the same adjacent vertices. So I had a finite 
set of graphs. In all cases the "rank-coloring conjecture"
was valid. In the meantime Alon and Seymour had found a counterexample
with chromatic number 32. While playing with these graphs and looking
at the tables of [Cvetkovic, Doob, Sachs 1978] I get my cograph 
conjecture.
Using the construction scheme of Lovasz I randomly generated graphs upto 100
vertices. In all cases my conjecture holds. So I only had numerical evidence.

The P_5 is the smallest rank-deficient graph not due to equal columns.


N. Alon, P. D. Seymour;
  A counterexample to the rank-coloring conjecture,
  Journal of Graph Theory 13:4 (1989) 523-525

--
mailto:Torsten.Sillke@uni-bielefeld.de
http://www.mathematik.uni-bielefeld.de/~sillke/