I am an undergraduate participant of Research Experience for Undergraduates at Dimacs, Rutgers.

The other members are Ondra Bílka, Eva Jelínková Zuzka Safernová, Petr Škoda, Jan Volec, and a graduate student Vítek Jelínek. We are from DIMATIA, Charles University in Prague.

I study Discrete Models and Algorithms on the Faculty of Maths and Physics of Charles University. Currently I am in the fourth year of the Magister degree study.

My scientific interests include graph theory, combinatorics, game theory, algorithms,
logic and functional languages.
The others are books, hiking, various games, philosophy, music, programming, traveling and cooking.

You can find more about me on my my homepage.

The entire czech group is working on several problems. They are described on our individual webpages.

We are working under the supervision of Mario Szegedy, Dan Cranston and Padmini Mukkamala.

It is a well-known fact that all planar graphs can be vertex-colored using only 4 colors while
general nonplanar graphs require arbitrarily many.
A natural question is to ask how "nonplanar" can the graph be and still be colorable by a limited
number of colors. Some bounds on the number of colors can be deduced from *crossing-number*
(the least number of crossings in any drawing of the graph).
In this problem we do not limit the number of the crosings but rather make all the crossings
independent.

In a fixed drawing of a graph into a plane, every quadruple of vertices
`(a,b,c,d)` where the edges `ac` and `bd` cross is called a *crossing*.
Two crossings are *independent* if the respective quadruples are disjoint.

The graph `G` admits a *planar drawing with independent crossings* if it can be drawn into
plane so that all the crossings are independent. In this summary we call `G`
*almost planar*.

The conjecture is that all almost planar graphs are 5-colorable.
This conjecture and the definition of independent crossings were introduces in the paper:

*M. O. Albertson*:Chromatic Number, Independence Ration, and Crossing Number,
*Ars Mathematica Contemporanea, Vol 1, No 1 (2008)*.

Known results include the observations taht every almost planar graph on `n`
vertices has at most `n/4` independent crossings, so it is 6-degenerated and hence 7-colorable.
Albertson has shown that all almost planar graphs are also 6-colorable and `K _{5}`
is almost planar and is not 4-colorable. The question of
5-colorability remains open (as of 6

We have proven that all the vertex-minimal counterexamples have these properties:

- All vertices have degree at least 5.
- In every drawing every triangle has either empty interior or exterior.
- In every drawing in every quadrangle nonincident with a crossing either the interior or the exterior of the quadrangle contains no vertex.
- The graph is vertex-4-connected.

Kelly-width is one of the three generalizations of tree-width for oriented graphs. The other two are
*DAG-width* and *oriented treewidth*. Kelly-width can be characterized in three
different ways - by elimination schemes, by monotone cop&robber games and by
DAG-decompositions with guards. Kelly-width is also directly connected to the elimination-width.

*Elimination scheme* is a linear order of the vertices of the graph. We can look at it
as an order in which to eliminate the vertices. Let us denote `N ^{+}(v)` all the vertices
from which there is an edge to

The *elimination-width* of an order is the maximum size of `N ^{-}(v)`
(the outdegree of

The *elimination-width* of a graph is the minimal elimination-width over all elimination schemes.
The *kelly-width* of a graph is its elimination-width plus 1.

Another way to define the kelly-width of a graph is the minimal number of cops sufficient to capture an invisible and lazy robbber with a monotone strategy where the cops can "teleport" but must announce their destination position to the robber, who moves arbitrarily only if some cop moves onto his current position.

For details on the game and the definition of decompositions with guards see the
paper of

*P. Hunter, S. Kreutzer*: Digraph Measures: Kelly Decompositions, Games, and Orderings.
*SODA 2007*.

Graphs with kelly-width at most 2 can be recognized in linear time. The hardness of recognizing graphs
of kelly width at most 3 is open (as of 8^{th} of July 2008).

We did not come up with any new results. We observed a polynomial algorithm recognizing
graphs of kelly-width 1 and 2, however this result was already published by
*D. Meister, J. A. Telle and M. Vatshelle* in their paper

Characterization and Recognition of Digraphs of Bounded Kelly-width,
*Graph-Theoretic Concepts in Computer Science, pp. 270-279*.

The slides for the presentation I gave at DIMACS REU 2008 Final presentations are presented here. They do capture neither the problem nor our results, but still may be useful.