2-Role assignments on triangulated graphs

✍ Scribed by Li Sheng

• Book ID: 104325776
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 267 KB
• Volume: 304
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00084-7

✦ Synopsis

If G is a graph, a k-role assignment is a function mapping each vertex into a role, a positive integer 1; 2; : : : ; k, so that if x and y have the same role, then the sets of roles assigned to their neighbors are the same. A graph is called a triangulated graph if it contains no chord-less cycle of four or more vertices. One interesting type of triangulated graph is the indi erence graph, that is a graph for which we can ÿnd a function on its vertex set so that if x and y are adjacent, then their assigned function values are close. We study 2-role assignments for triangulated graphs. We provide a "greedy" algorithm for ÿnding a 2-role assignment on a connected, non-bipartite triangulated graph with at most one pendant vertex. We characterize indi erence graphs that have a 2-role assignment.