Jenő Lehel
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Jenő Lehel has a total of 24 co-authors. Here are the top co-authors by number of shared publications:
- András Gyárfás
Hungarian Academy of Sciences
4 shared publications - Frédéric Maffray
G-SCOP_OC - Optimisation Combinatoire (46 Avenue Félix Viallet 38001 GRENOBLE Cedex 1 - France)
2 shared publications Kiyoshi Yoshimoto
Nihon University, Tokyo, Japan
2 shared publications- Myriam Preissmann
C.N.R.S., Laboratoire G-SCOP, Grenoble, France
2 shared publications Ralph J. Faudree
The University of Memphis, Memphis, USA
2 shared publications- Alex Scott
Mathematical Institute University of Oxford Oxford UK
1 shared publication
Latest Publications
- 24 September 2015
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 32 (3) , 963-986
Locating Pairs of Vertices on a Hamiltonian Cycle in Bigraphs
- 24 September 2015
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 32 (3) , 963-986
Locating Pairs of Vertices on a Hamiltonian Cycle in Bigraphs
- 7 June 2013
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 30 (4) , 887-894
Note on Locating Pairs of Vertices on Hamiltonian Cycles
- 7 June 2013
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 30 (4) , 887-894
Note on Locating Pairs of Vertices on Hamiltonian Cycles
- Open Access
Around a biclique cover conjecture
We address an old (1977) conjecture of a subset of the authors (a variant of Ryser's conjecture): in every r-coloring of the edges of a biclique [A,B] (complete bipartite graph), the vertex set can be covered by the vertices of at most 2r-2 monochromatic connected components. We reduce this conjecture to design-like conjectures, where the monochromatic components of the color classes are bicliques [X,Y] with nonempty blocks X and Y. We prove this conjecture for r<6. We show that the width (the number of bicliques) in every color class of any spanning r-coloring is at most 2^{r-1} (and this is best possible).
Open AccessAround a biclique cover conjecture
We address an old (1977) conjecture of a subset of the authors (a variant of Ryser's conjecture): in every r-coloring of the edges of a biclique [A,B] (complete bipartite graph), the vertex set can be covered by the vertices of at most 2r-2 monochromatic connected components. We reduce this conjecture to design-like conjectures, where the monochromatic components of the color classes are bicliques [X,Y] with nonempty blocks X and Y. We prove this conjecture for r<6. We show that the width (the number of bicliques) in every color class of any spanning r-coloring is at most 2^{r-1} (and this is best possible).
- 21 July 2010
- Published by Wiley in Journal of Graph Theory
- Vol. 65 (1) , 16-34
List multicoloring problems involving the k‐fold Hall numbers
We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ⌈5k/3⌉; furthermore, the same is not true with shorter list lengths. In terms of h(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h(k)(C4)=2k−⌊k/3⌋. For longer cycles it is known that h(k)(Cn)=2k, for n odd, and 2k−⌊k/(n−1)⌋≤h(k)(Cn)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C4). We prove that if G is the diamond (a four‐cycle with a diagonal), then h(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.
- 21 July 2010
- Published by Wiley in Journal of Graph Theory
- Vol. 65 (1) , 16-34
List multicoloring problems involving the k‐fold Hall numbers
We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ⌈5k/3⌉; furthermore, the same is not true with shorter list lengths. In terms of h(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h(k)(C4)=2k−⌊k/3⌋. For longer cycles it is known that h(k)(Cn)=2k, for n odd, and 2k−⌊k/(n−1)⌋≤h(k)(Cn)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C4). We prove that if G is the diamond (a four‐cycle with a diagonal), then h(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.
- 7 April 2009
- Published by Wiley in Journal of Graph Theory
- Vol. 61 (2) , 140-156
Maximum directed cuts in digraphs with degree restriction
- 7 April 2009
- Published by Wiley in Journal of Graph Theory
- Vol. 61 (2) , 140-156
Maximum directed cuts in digraphs with degree restriction
- 1 March 2008
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 98 (2) , 342-358
Monochromatic Hamiltonian Berge-cycles in colored complete uniform hypergraphs
- 1 March 2008
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 98 (2) , 342-358
Monochromatic Hamiltonian Berge-cycles in colored complete uniform hypergraphs
- Open Access
Maximum directed cuts in digraphs with degree restriction
For integers m,k >= 1, we investigate the maximum size of a directed cut in directed graphs in which there are m edges and each vertex has either indegree at most k or outdegree at most k.
Open AccessMaximum directed cuts in digraphs with degree restriction
For integers m,k >= 1, we investigate the maximum size of a directed cut in directed graphs in which there are m edges and each vertex has either indegree at most k or outdegree at most k.
- 27 October 2006
- Published by Wiley in Journal of Graph Theory
- Vol. 55 (1) , 1-13
Maximum directed cuts in acyclic digraphs
It is easily shown that every digraph with m edges has a directed cut of size at least m/4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of the largest directed cut in acyclic digraphs, and prove a number of related results concerning cuts in digraphs and acyclic digraphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 1–13, 2007
- 27 October 2006
- Published by Wiley in Journal of Graph Theory
- Vol. 55 (1) , 1-13
Maximum directed cuts in acyclic digraphs
It is easily shown that every digraph with m edges has a directed cut of size at least m/4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of the largest directed cut in acyclic digraphs, and prove a number of related results concerning cuts in digraphs and acyclic digraphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 1–13, 2007
- 4 May 2006
- Published by Wiley in Journal of Graph Theory
- Vol. 54 (1) , 1-12
Finding a monochromatic subgraph or a rainbow path
For simple graphs G and H, let f(G,H) denote the least integer N such that every coloring of the edges of KN contains either a monochromatic copy of G or a rainbow copy of H. Here we investigate f(G,H) when H = Pk. We show that even if the number of colors is unrestricted when defining f(G,H), the function f(G,Pk), for k = 4 and 5, equals the (k − 2)‐ coloring diagonal Ramsey number of G. © 2006 Wiley Periodicals, Inc. J Graph Theory
- 4 May 2006
- Published by Wiley in Journal of Graph Theory
- Vol. 54 (1) , 1-12
Finding a monochromatic subgraph or a rainbow path
For simple graphs G and H, let f(G,H) denote the least integer N such that every coloring of the edges of KN contains either a monochromatic copy of G or a rainbow copy of H. Here we investigate f(G,H) when H = Pk. We show that even if the number of colors is unrestricted when defining f(G,H), the function f(G,Pk), for k = 4 and 5, equals the (k − 2)‐ coloring diagonal Ramsey number of G. © 2006 Wiley Periodicals, Inc. J Graph Theory
- 1 January 2004
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 13 (3) , 311-317
Longest Paths in Circular Arc Graphs
We show that all maximum length paths in a connected circular arc graph have non-empty intersection.
- 1 January 2004
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 13 (3) , 311-317
Longest Paths in Circular Arc Graphs
We show that all maximum length paths in a connected circular arc graph have non-empty intersection.