Luis Gustavo da Soledade Gonzaga

dblp:250/6109 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2023
0000-0003-2070-717XORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2023 The Overfull Conjecture on split-comparability and split-interval graphs
Luis Gustavo da Soledade Gonzaga, Jadder Bismarck de Sousa Cruz, Sheila Morais de Almeida, Cândida Nunes da Silva
Discret. Appl. Math.1
2021 The chromatic index of split-interval graphs
abstract
The chromatic index of a graph G, χ'(G), is the least number of colors of some edge coloring of G such that no two adjacent edges have the same color. Given a graph G and an integer k, to decide if χ'(G) ≤ k is NP-complete. A graph is an interval graph if it represents the intersection relation of a set of closed intervals in R. A graph is a split graph if its vertex set can be partitioned into a clique and an independent set. A graph is split-interval if it is simultaneously an interval and a split graph. In this paper we show how to determine the chromatic index of all split-interval graphs. Our proof leads to a polynomial-time algorithm to deciding if χ'(G) ≤ k given an integer k and a split-interval graph G.
Luis Gustavo da Soledade Gonzaga, Sheila Morais de Almeida, Cândida Nunes da Silva, Jadder Bismarck de Sousa Cruz
LAGOS1