Forbidden subgraphs and prohibited colorings for vertex identification in graphs
- Title
- Forbidden subgraphs and prohibited colorings for vertex identification in graphs
- Creator
- Iyer, Akshay Vishnuprakash; Kureethara, Joseph Varghese
- Description
- A red-white coloring of a graph G of diameter d is done by assigning the colors red and white to the vertices of the graph such that, there should be at least one red vertex. Then, each of the vertices is assigned a vector of length d called code in which the value of ith coordinate is equal to the number of red-colored vertices at distance i from this vertex, i ? {1, 2, 3,,d}. A red-white coloring when the code assigned to each vertex is different than that coloring is called an ID-coloring and a graph which has an ID-coloring is an ID-graph. The minimum number of vertices required to be colored red to get an ID-coloring is called the ID-number. ID-coloring is not possible for all graphs. There exist many properties which prevent ID-coloring. In this paper, we explore some forbidden induced subgraphs and certain prohibited red-white colorings which prevent the existence of ID-coloring. 2025 World Scientific Publishing Company.
- Source
- Discrete Mathematics, Algorithms and Applications;Issue;;Article No.;2550092;
- Date
- 01-01-2025
- Publisher
- World Scientific
- Subject
- distance; Graph coloring; ID-coloring; ID-graph
- Coverage
- Iyer A.V., Department of Mathematics, CHRIST (Deemed to be University), Karnataka, Bengaluru, 560029, India; Kureethara J.V., Department of Mathematics, CHRIST (Deemed to be University), Karnataka, Bengaluru, 560029, India
- Rights
- Restricted Access; Hardcopy may be available in the library
- Relation
- ISSN: 17938309;
- Format
- online
- Language
- English
- Type
- Article
Collection
Citation
Iyer, Akshay Vishnuprakash; Kureethara, Joseph Varghese, “Forbidden subgraphs and prohibited colorings for vertex identification in graphs,” CHRIST (Deemed To Be University) Institutional Repository, accessed June 18, 2026, https://archives.christuniversity.in/items/show/23044.
