30 April 2025
10:00 Master's Defense fully remotely
Topic on
On (2, 1)-colorings in outplanar graphs
Student
Adilson Luis Jönck Júnior
Advisor / Teacher
Christiane Neme Campos
Brief summary
This dissertation addresses improper colorings, an extension of the classical area of graph coloring, with emphasis on (2,1)-colorings applied to outlier graphs. Outlier graphs are planar graphs that admit an embedding in the plane such that all their vertices are located on the boundary of the outer face. Improper colorings generalize proper colorings, allowing adjacent vertices to receive the same color, but under certain restrictions. In particular, in (2,1)-colorings, two colors are assigned to the vertices, and each vertex can have, at most, one neighbor with the same color as the one assigned to it. Initially, classical concepts and the basic notation of Graph Theory are introduced. Then, definitions and results relevant to the context of the research developed in this work are presented. In particular, structural properties of outlier graphs and variants of improper colorings are established. A history of the existing research in the studied area is also presented. The results obtained in this research are presented in Chapter 3. It was demonstrated that outplane graphs with at most three triangular faces admit (2,1)-colorings. In addition, families of outplane graphs with more than three triangular faces that admit and others that do not admit (2,1)-colorings were presented, evidencing that the limit found is fair. For maximal outplane graphs, the results obtained are more definitive: necessary and sufficient conditions were established for these graphs to admit (2,1)-colorings.
Examination Board
Headlines:
| Christiane Neme Campos | IC / UNICAMP |
| Lehilton Lelis Chaves Pedrosa | IC / UNICAMP |
| Claudia Linhares Sales | DC/UFC |
Substitutes:
| João Meidanis | IC / UNICAMP |
| Sheila Morais de Almeida | UTFPR |