
Some of my favourite problems on cycles and colorings
Paul Erdős ^{1)}
1)  Mathematical Institute, Hungarian Academy of Sciences; Realtanoda u. 1315; H1053 Budapest; HUNGARY. 
Six problems concerning graph cycles and colourings are presented.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 79.
 

More about the weight of edges in planar graph
Oleg Borodin ^{1)}
1)  Institute of Mathematics, Siberian Branch of Russian Academy of Sciences; Novosibirsk, 630090; RUSSIA. 
The weight of an edge in a plane graph is the degree sum of its end vertices. Recent results on the minimum weight of all edges, denoted by $w$, of those incident with a triangle, $w^{*}$, and those incident with two triangles, $w^{*\ast}$, in a plane graph are discussed. It is proved that if a normal plane map has $w^{*\ast}=∞$, then either $w^{*}≤ 9$ or $w≤ 8$, where both bounds are sharp.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 1114.
 

Fast exact colouring algorithms
Ingo Schiermeyer ^{1)}
1)  RWTH Aachen, Department C of Mathematics; Templergraben 55; D52056 Aachen; GERMANY. 
In this paper we describe and analyze four improved algorithms for deciding the $3, 4, 5$ and $6$ Colourability problem. If $G$ is a simple graph on $n$ vertices then we will show that these algorithms test a graph for $3, 4, 5$ or $6$Colourability, i.e., an assignment of three, four, five or six colours to the vertices of $G$ such that two adjacent vertices obtain different colours, in less than $O(1,398^{N})$, $O(1,585^{n})$, $O(1,938^{n})$ or $O(2,155^{n})$ steps.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 1530.
 

Unifying results on Hamiltonian clawfree graphs
Hajo J. Broersma ^{1)}, Zdeněk Ryjacek ^{2)}, Ingo Schiermeyer ^{3)}
1)  Faculty of Mathematical Sciences, University of Twente; P.O.Box 217; 7500 AE Enschede; NETHERLAND.  2)  Katedra matematiky, Zapadoceska univerzita; Univerzitni 22; 306 14 Plzen; CZ.  3)  RWTH Aachen, Department C of Mathematics; Templergraben 55; D52056 Aachen; GERMANY. 
This work was motivated by many (recent) papers on hamiltonicity of clawfree graphs, i.e., graphs that do not contain $K_{1,3}$ as an induced subgraph. By combining ideas from these papers with some new observations, we unify several of the existing sufficiency results, using a new sufficient condition consisting of seven subconditions. If each pair of vertices at distance two of a 2connected clawfree graph $G$ satisfies at least one of these subconditions, then $G$ is Hamiltonian. We also present infinite classes of examples of graphs showing that these subconditions are, in some sense, independent.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 3139.
 

Shortness exponents for some families of maximal planar graphs
Peter John Owens ^{1)}
1)  Department of Mathematics and Statistics, University of Surrey; Guildford GU2 5XH; U. K.. 
It is shown that the family of maximal planar simple graphs such that every vertex has valency 5 or $q≥ 14$, not only has nonHamiltonian members but even has a shortness exponent less than one.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 4150.
 

The crossing number of $K_{2,3}× P_{n}$ and $K_{2,3}× S_{n}$
Marian Klesc ^{1)}
1)  Katedra matematiky FEI TU, Hlavna 6, 042 00 Kosice, Slovakia. marian.klesc@tuke.sk 
There are several known exact results on the crossing number of Cartesian product of paths or cycles with ``small'' graphs. Here we determine the crossing number of $K_{2,3}× P_{n}$ and $K_{2,3}× S_{n}$ where $P_{n}$ and $S_{n}$ are the path and the star with $n$ edges, respectively.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 5156.
 

Isomorphism classes of one edge transformed graphs
Krystyna T. Balińska ^{1)}, Louis V. Quintas ^{2)}
1)  Computer Science Center, Technical University of Poznań; Pl. M. SklodowskejCurie 5; 60965 Poznań; POLAND.  2)  Mathematics Department, Pace University; New York, NY 10038; U. S. A.. 
The isomorphism classes and the chromatic numbers of the one edge deleted subgraphs and the one edge extended supergraphs of a graph are studied. Graphs are determined having the property that either every one edge deleted subgraph or every one edge extended supergraph is isomorphically distinct. The following is one of a number of open problems considered. For a given chromatic number $χ_{0}$, characterize the class of graphs $\langle G\rangle$ such that $χ(G)=χ_{0}$ and every one edge extended supergraph of $G$ has chromatic number $χ_{0}$. Similarly, characterize the class of graphs $\langle H\rangle$ such that $χ(H)=χ_{0}$ and every one edge extended supergraph of $H$ has chromatic number $χ_{0}+1$.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 5767.
 

On a conjecture of Erdős, Rubin and Taylor
Zsolt Tuza ^{1)}, Margit Voigt ^{2)}
1)  Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 1317; H1111 Budapest; HUNGARY. tuza@lutra.sztaki.hu  2)  Institut für Mathematik, Technische Universitat Ilmenau; D98684 Ilmenau; GERMANY. 
A graph $G$ with vertex set $V$ and edge set $E$ is called $(a, b)$choosable if for any assignment of lists $L(v)$ of colours to the vertices $v$ of $G$ with $L(v)=a$ it is possible to choose subsets $C(v)\subset L(v)$, $C(v)=b$ for every $v\in V$ such that $C(u)\cap C(v)=\emptyset$ for all $uv\in E$. In 1979, Erdős, Rubin and Taylor [P. Erdős, A. L. Rubin, H. Taylor: Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics Graph Theory and Computing, Arcata, California, 1979, Congressus Numeratium 26 (1979), 125–157] raised the conjecture that every $(a, b)$choosable graph $G$ is also $(am, bm)$choosable for all $m>1$. We investigate the case $b=1$, presenting some classes of $(a, 1)$choosable graphs for which $(am,m)$choosability can be proved for all $m$.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 6982.
 

The induced path number of a complete multipartite graph
Izak Broere ^{1)}, Elizabeth Jonck ^{2)}, Margit Voigt ^{3)}
1)  Department of Mathematics, Rand Afrikaans University; P.O.Box 524; Auckland Paark; 2006 SOUTH AFRICA.  2)  Department of Mathematics, Rand Afrikaans University; P. O. Box 524; Auckland Park; 2006 SOUTH AFRICA.  3)  Institut für Mathematik, Technische Universitat Ilmenau; D98684 Ilmenau; GERMANY. 
The induced path number $ρ(G)$ of a graph $G$ is defined as the minimum number of subsets into which the vertex set of $G$ can be partitioned so that each subset induces a path. In this paper we determine the induced path number of a complete $l$partite graph.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 8388.
 

Some open problems in optimal digraphs
Mirka Miller ^{1)}
1)  Department of Computer Science, The University of Newcastle; NSW 2308 AUSTRALIA. 
The Moore bound for a digraph of maximum outdegree $d$ and diameter $k$ is $M_{d, k}=1+d+…+d^{k}$. It is known that digraphs of order $M_{d, k}$ do not exist for $d>1$ and $k>1$. This being the case, for $d>1$ and $k>1$, we consider digraphs which are `close' to Moore, that is, digraphs with maximum outdegree $d≥ 2$, diameter $k≥ 2$ and order $n(d, k)=M_{d, k}Δ_{d, k}$ where $Δ_{d, k}$ is the minimum possible `defect' for given $d$ and $k$. Furthermore, we consider the construction of diregular digraphs with minimum diameter, given the order and degree. At the end of each section we present a number of open problems.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 8996.
 

On the minimal number of separating 3cycles in nonhamiltonian maximal planar graphs
Thomas Böhme ^{1)}, Jochen Harant ^{2)}, Michal Tkac ^{3)}
1)  Institut Für Mathematik, TU Ilmenau; PF 327,G98684 Ilmenau; Germany.  2)  Institute of Mathematics, Technical University Ilmenau; Postfach 327; D98684 Ilmenau; GERMANY.  3)  Strojnicka fakulta TU, Letna 9; 040 00 Kosice. 
A well known theorem of H. Whitney states that every maximal planar graph without separating 3cycles is Hamiltonian. The problem discussed here is how many separating 3cycles such a graph must have to be nonHamiltonian.
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 97102.
 

Problem
HeinzJürgen Voss ^{1)}
1)  Technische Universitat Dresden, Abteilung Mathematik; Institut für Algebra; Mommsenstrasse 13; 01062 Dresden; GERMANY. 
Tatra Mountains Mathematical Publications. Volume 9, 1996, No. 3: 103104.
 