IJPAM: Volume 38, No. 3 (2007)

THE NUMBER OF CRITICAL COLORINGS
FOR SOME RAMSEY NUMBERS

Tomasz Dzido$^1$, Robert Fidytek$^2$
$^{1,2}$Institute of Mathematics
University of Gdansk
Wita Stwosza 57, Gdansk, 80-952, POLAND
$^1$e-mail: tdz@math.univ.gda.pl
$^2$e-mail: fidytek@manta.univ.gda.pl


Abstract.We enumerate all critical $(K_4,K_5-e;18)$ and $(K_5,K_4-e;15)$-colorings. This gives a good starting point for an attack on the problem of improving the bounds on the Ramsey number $R(K_5,K_5-e)$, which is one of the three remaining open cases for graphs on at most five vertices.

Received: May 10, 2007

AMS Subject Classification: 05C55, 05C15

Key Words and Phrases: edge coloring, Ramsey number

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 38
Issue: 3