
BMe Research Grant 

BMe Research Grant  2011
3^{rd} Prize
The topic of my PhD research is graph theory, more closely various problems on graph coloring. I investigate the asymptotic behaviour of graph parameters related to colouring, and also covering problems associated with edge colouring.
My PhD supervisor is Gábor Simonyi,
a professor of BUTE Department of Computer Science and Information Theory
and a research fellow of the Alfréd Rényi Institute of Mathematics.
I carry out my research work at BUTE Department of Computer Science and Information Theory. The main research topics of our department include the matroid theory, complexity theory (parametrized complexity, efficiency of quantum computing), reliability of communication networks, VLSI routing and declarative programming. Many of us are doing research on combinatorics and graph theory, for example on questions on Hamiltonian cycles or on crossing numbers.
History and context of the researchGraph theory is an important branch of mathematics, more precisely of combinatorics. Its main concept is the graph, which consists of a collection of vertices and of edges that pairwise connect vertices. Such structures play an important role in various areas of life. Graphs can be used to represent social or communication networks, structure of molecules, computing processes. Moreover, the theory of these structures is often an essential tool to the solution of questions in several fields. The chromatic number of a graph is the minimum number of colours which can be assigned to the vertices such that no two adjacent vertices share the same colour. This is one of the most intensively investigated graph parameters, and its behaviour is only understood is some situations, but is totally unknown in most of the cases. One of main applications of colouring is the scheduling theory. (In a very basic example, the vertices of the graph represent the computer tasks to schedule, and the edges correspond those pairs which are required to run on different machines. In this case the minimum number of machines in a proper scheduling is the chromatic number of the associated graph.) The popular puzzle, the Sudoku can also be formulated as a colouring problem of a special graph. 

In my PhD research I concentrate on two larger topics of graph colouring problems: the asymptotic behaviour of graph parameters for different graph powers and various covering problems of edgecoloured graphs. I started working on graph colouring problems in the frame of Students' Scholarly Circles, as a third year undergraduate. I also prepared my master thesis in this topic, which I continued since 2008 as a PhD student. For my bachelor thesis as a computer engineering student I am developing softwares which help my research in graph colouring problems. 
Asymptotic values of graph
parameters for graph powers
Several graph parameters show an interesting
behaviour when they are investigated for different powers of graphs. One
of the most famous examples of such behaviour is that of the Shannon
capacity of graph [Shannon], which is the theoretical upper limit of channel capacity for
errorfree coding in information theory. This concept can be derived in the
following way.
Let us consider a channel on which one can transmit five characters. Because of the noise in the channel some pairs or characters may be confused during the transmission. The graph on the figure represents the channel: the vertices are the characters, and two vertices are connected with en edge if they can be confused. (By sending a character 'k' the receiver may get 'h' or 'b' in stead of 'k', but he cannot receive 'n' or 'p'.) It is easy to see that to realize a decodable, errorfree
coding (in a simple case) we should choose pairwise distinguishable
characters. So we can use at most two characters, as there are no more
characters without an edge between them. 
The graph of a simple channel, a pentagon. 
An independent set of the second power of the pentagon for normal product. 
If we transmit more characters together on the channel, then we can increase the information rate (in units of information per unit time). The following five character pairs are pairwise distinguishable: 'kk', 'hn', 'nb', 'ph', 'bp', since any two of them are distinguishable in the first or in the second element. Combining these pairs using characters we can transmit different messages as well. It was an open problem for a long time whether or not this is the optimum, and a celebrated result of Lovász is that the Shannoncapacity of the pentagon is , that is, one can not send more then distinguishable messages with characters [Lovász]. 
Shannoncapacity of a graph is defined as the
normalized limit of the independence number under the socalled normal power.
The independence number of a graph is the size of the largest independent set
where an independent set is a subset of the vertex set which contains no edge.
The normal product of graphs is defined on set of pairs formed by the vertex
set of the two base graphs, and we connect two pairs if the corresponding
elements are equal or form an edge in both coordinates. (This product describes
the confusability relation of messages written above.)
We consider similar questions in [1], [2], [3], [5], where we investigate the asymptotic behaviour of colouringrelated graph parameters for different graph powers in the articles.
Covering problems of
edgecoloured graphs
In my PhD studies I also investigated covering problems of edgecoloured graphs. Probably the most famous open question in this area is the Ryser conjecture (appeared in the Thesis of his student, Henderson [Henderson]). An interesting special case of the conjecture states that if one colours the edges of a complete graph with colours, then the vertex set can be covered by the vertices of at most monochromatic connected components [Gyárfás].
Covering with
components is easy, as choosing a vertex as a centre, the
corresponding stars in different colours cover the whole vertex set of graph.
The conjecture states that one less component is also enough in any
case.
In the works [4], [6], [7] we prove results on covering problems of edgecolored graphs.
Asymptotic values of graph
parameters for graph powers
The Hallratio of a graph is the fraction of the number of vertices and the independence number maximized over all subgraphs of the graph. (For example, in the case of the fivewheel shown above, the value of this parameter is 3). The introduction of this concept was motivated by colouring problems [Cropper et al]. Simonyi investigated the asymptotic value of this graph parameter for different graph powers. He showed that for normal power the asymptotic value is the Witsenhausenrate, while for conormal power we obtain the fractional chromatic number as the limit of the sequence [Simonyi]. The Witsenhausenrate is defined as the normalized asymptotic value of the chromatic number, and it also plays role in information theory.
The fractional chromatic number is the fractional relaxation of the chromatic number. This means that we put real weights on the independent sets of the graph, such that for every vertex the sum of the weights corresponding to those independent sets which contain that vertex is at least 1, and with this condition we want to minimise the total weight put on all independent sets of the graph. The value of this minimum is the fractional chromatic number of the graph. (In a proper colouring of a graph, the vertices coloured with the same
colour form an independent set, thus this concept is a generalization of the chromatic number concept. If we only consider
integer values (0 or 1) in the definition, then we get back the concept of chromatic
numbers.) 
the fractional chromatic number of the graph is 3,5. 
In my master thesis I proved the conjecture of
Simonyi stating that the fractional chromatic number is the asymptotic value for lexicographic
power, too [1]. The analog question for the direct power is
different from the previous ones in many aspects, and its confirmation is one of
my recent results [5]. The proof uses a recent result of Zhu that he showed while proving the fractional version of Hedetniemi's
conjecture [Zhu].
I also investigated a similar graph parameter,
the independence ratio which is the ratio of the independence number and the
number of vertices. I determined its asymptotic value for direct power in case
of complete multipartite graphs [2], answering the question of Brown, Nowakowski and Rall [Brown et al]. In the proof I revealed the structure of
independent sets and their neighbourhood in the graph power.
Similar questions are discussed in [3] coauthored with Brightwell, Cohen, Fachini, Fairthorne, Körner, Simonyi. The topic of that article is a combinatorial puzzle created by Körner and Malvenuto [Körner et al] and of further interest is that we use results related to a sequence [André, OEIS] already investigated in the 19th century.
Covering problems of
edgecoloured graphs
An edgecolouring of a graph is called a
Gallai colouring if there is no completely multicoloured triangle. (We can
use as many colours as we want.) Investigating comparability graphs, Gallai
proved remarkable theorems about edge colouring satisfying this condition
[Gallai], and later this concept turned out to be
relevant in several other areas of graph theory. A basic property of
Gallai colourings is that for any complete graph one
can find a monochromatic component which covers the whole vertex set of
the graph. Gyárfás and Sárközy showed that if we colour the edges of a not
necessarily complete graph so that no 3coloured triangles appear then
there is still a large monochromatic connected component whose guaranteed
size is proportional to vertex number, where the proportion depends only
on the independence number of the graph. [Gyárfás et al]. 
A Gallai colouring of the complete graph on seven vertices. 
With Gyárfás and Simonyi we worked on the generalization of this result [4]. We proved that considering a Gallai colouring of any graph with a fixed independence number we can also cover the whole vertex set of the graph with ﬁnitely many connected monochromatic subgraphs. During the research, another problem about the domination number of multipartite digraphs appeared, whose solution was the key to the proof of the previous statement.
As a continuation of this research with Gyárfás, Fujita and Furuya, we proved the partitioning version of this problem: we showed that the vertex set of the base graph can also be covered by a disjoint union of the vertex sets of finitely many monochromatic connected components, whose number depends only on the independence number of the graph. We also investigated further extensions of the problem [6].

The following conjecture due to Gyárfás and Lehel is an analogue version of the Ryser conjecture for biparite graphs [Gyárfás, Lehel]. This conjecture states that if we colour the edges of a complete bipartite graph with colours then we can always find at most monochromatic connected components whose vertices cover the whole vertex set of the biparite graph. Covering with monochromatic components is easy, and there is an example showing that components are needed. The statement of the conjecture is clear for , and as a joint work with Chen, Fujita, Gyárfás and Lehel we proved the statement for and , too [7]. 
As a joint work with Gyárfás, Fujita and Furuya
we are investigating the possible extensions of the recent result of Király
which can be considered as a generalization of the above special case of the
Ryser conjecture for hypergraphs. [Király].
We are working on further edgecolouring problems
with Lesniak and Fujita [8], where we already have some partial results.
I have 3 published, 1 accepted and 1 submitted articles. I have 2 further publications in manuscript (which we plan to submit soon) and another 1 in preparation.
Publications
[1] Á. Tóth. On the ultimate lexicographic Hallratio. Discrete Math., 309 12 (2009), 3992–3997.
article, journal
version, related
talk
[2] Á. Tóth. The
ultimate categorical independence ratio of complete multipartite graphs.
SIAM J. Discrete Math., 23 4 (2009), 1900–1904.
article, journal version, related talk
[3] G. Brightwell, G. Cohen, E. Fachini, M. Fairthorne, J. Körner, G. Simonyi, Á. Tóth. Permutation capacities of families of oriented infinite paths. SIAM J. Discrete Math., 24 2 (2010), 441–456.
[4] A. Gyárfás, G.
Simonyi, Á. Tóth. Gallai colorings and domination in multipartite
digraphs. accepted for publication in Journal of Graph Theory
[5] Á. Tóth. On the
ultimate direct Hallratio. submitted to Graphs and Combinatorics
[6] S. Fujita, M.
Furuya, A. Gyárfás, Á. Tóth. Monochromatic tree partitions in edgecolored
graphs and hypergraphs. manuscript
[7] G. Chen, S. Fujita, A. Gyárfás, J. Lehel, Á.
Tóth. Around a biclique cover conjecture. manuscript
[8] L. Lesniak, S. Fujita, Á. Tóth. New
results on long monochromatic cycles in edgecolored complete graphs. In
preparation
Conference proceedings (their content is a part of the articles [1],[2],[5]):
Á. Tóth. Asymptotic values of graph parameters. Proceedings of the 6th HungarianJapanese Symposium on Discrete Mathematics and Its Applications, Budapest, 2009., 388–392.
Á. Tóth. On the asymptotic values of the Hallratio. Proceedings of
the 7th HungarianJapanese Symposium on Discrete Mathematics and Its
Applications, Kyoto, 2011., 470–472.
References
[André] D. André.
Développement de sec x and tg x. C. R. Math. Acad. Sci. Paris, 88 (1879),
965–979.
[Brown et al] J. I.
Brown, R. J. Nowakowski, D. Rall. The ultimate categorical independence ratio of
a graph. SIAM J. Discrete Math., 9 (1996), 290–300.
[Cropper et al] M. Cropper, M. S.
Jacobson, A. Gyárfás, L. Jenő. The Hall ratio of graphs and hypergraphs. Les
cahiers du Laboratoire Leibniz., 17, 2000.
[Gallai] T. Gallai. Transitiv orientierbare Graphen. Acta
Math. Sci. Hungar., 18 (1967), 25–66.
[Gyárfás] A. Gyárfás. Partition coverings and blocking sets in
hypergraphs. Commun. Comput. Autom. Inst. Hungar. Acad. Sci., 71
(1977)
[Gyárfás et al] A.
Gyárfás, G. N. Sárközy. Gallai colorings of noncomplete graphs. Discrete Math., 310 (2010), 977–980.
[Henderson] J. R. Henderson. Permutation decomposition of
(0,1)matrices and decomposition transversals. Ph.D. Thesis, Caltech
(1971)
[Király] Z. Király. Monochromatic
components in edgecolored complete uniform hypergraphs. Submitted.
[Körner et al] J. Körner and C.
Malvenuto. Pairwise colliding permutations and the capacity of infinite graphs.
SIAM J. Discrete Math., 20 (2006), 203–212.
[Lehel] J. Lehel. Ryser’s conjecture for linear
hypergraphs. manuscript, 1998.
[Lovász] L.
Lovász. On the Shannon capacity of a graph. IEEE Trans. Inform.,
25 (1979), 1–7.
[Shannon] C.
E. Shannon. The zerocapacity of a noisy channel. IRE Trans. Inform.
Theory, 2 (1956), 8–19.
[Simonyi]
G. Simonyi. Asymptotic values of the Hallratio for graph powers.
Discrete Math. 306 (2006), 2593–2601.
[Zhu] X. Zhu.
Fractional Hedetniemi's conjecture is true. European J. Combin. (2011),
doi:10.1016/j.ejc.2011.03.004
Links
BUTE Graduate School of
Mathematics and Computer Science, Department of Computer Science and Information
Theory
Useful links on the Wikipedia: graph theory, chromatic numer, fractional chromatic number, graph products.
The famous opened problems of the area: the Hedetniemi
conjecture, Ryser
conjecture.