General Information

Student: Veronika Steffanova 450 Charles University in Prague veronika.steffanova guess_what_is_here rutgers.edu $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, Tao-Ming 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), 309--316.
• D. Sakai, Labelling chordal graphs: distance two condition. SIAM J. Disc. Math. 7 (1994), 133--140.
• J.R. Griggs; R.K. Yeh, Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5 (1992), 586--595.

Current activities

First week

• Introduction, definition
• Presentation
• Search the articles.

Second week

• First observations.
• 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 NP-complete 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