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/