General Information
Student: 
Veronika Steffanova 
Office: 
450 
School: 
Charles University in Prague 
Email: 
veronika.steffanova guess_what_is_here rutgers.edu 
Projects: 

$L(p,q)$labeling of Interval Graphs 
$L(p,q)$labeling of Interval Graphs
Project Description
Interval graphs are intersection graphs of a family of intervals of real numbers. $L(p,q)$labeling of a graph $G$ is a mapping $l \colon V_G \to X$ where $X \subset \mathbb{Z}$ such that
 $f(u)  f(v) \geq p$ whenever the vertices $u$ and $v$ are connected by an edge,
 $f(u)  f(v) \geq q$ whenever there exists a vertex $w$ such that both $u$ and $v$ are neighbors of $w$.
Finally, span of graph $G$ is the smallest number $k$ such that there exists $L(p,q)$labeling of $G$ using $X = \{ 0, \dots, k \}$. In this project, we look for a formula for the span of $L(2,1)$ for the class of interval graphs and its connection to the chromatic number of the graph and the maximum degree of the graph.
Previous work
 Peter Che Bor Lam, Guohua Gu, Wai Chee Shiu, TaoMing Wang: On Distance Two Labelling of Unit Interval Graphs here.
 G.J. Chang; D. Kuo, The L(2,1)labeling problem on graphs. SIAM J. Discrete Math. 9 (1996), 309316.
 D. Sakai, Labelling chordal graphs: distance two condition. SIAM J. Disc. Math. 7 (1994), 133140.
 J.R. Griggs; R.K. Yeh, Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5 (1992), 586595.
Current activities
Current activities
First week
 Introduction, definition
 Presentation
 Search the articles.
 Read the articles.
Second week
 First observations.
 Reading the articles.
 Bridge workshop
 Talks
Third week
 Try to find an algorithm for labeling interval graphs.
 Upper bound from the algorithm.
 Bridge workshop
 Talks
Fourth week
 Lower bound.
 Bridge workshop
 Talks
 Cultural day
Fifth week
 $L(2,1)$  labeling is NPcomplete on interval graphs
 Improving the upper bound to be tight.
 Bridge workshop
 Looking for example for more general example for lower bound
Sixth week
 Looking for example for more general example for lower bound
 Path generalization
 Star generalization
 Bridge workshop
Seventh week
 Writing the report
 Looking for an example with higher chromatic number
 Preparing the presentation for Friday
 Talks
More details
Coworkers
Presentations
Additional Information
My Mentor
Professor James Abello
http://www.mgvis.com/
http://www.mgvis.com/AbelloVitaResearchOct08.html