Tomáš Gavenčiak

REU 2008

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.

About me

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.

Coloring almost-planar graphs


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 K5 is almost planar and is not 4-colorable. The question of 5-colorability remains open (as of 6th of July 2008).

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

Recognizing Graphs of Kelly-Width at most 3


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 v and N-(v) all the vertices to which there is an edge from v. Whenever we eliminate a vertex v, we delete v and add an oriented edge from every vertex in N+(v) to every vertex in N-(v).

The elimination-width of an order is the maximum size of N-(v) (the outdegree of v) over all eliminated vertices, measuring in the graph just before deleting v.

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 8th 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.

The page was updated on 8th of July 2008.