On Total and Edge-colouring of Proper Circular-arc Graphs

  • João Pedro W. Bernardi
  • Sheila M. de Almeida
  • Leandro M. Zatesko
DOI: https://doi.org/10.5753/etc.2018.3557

Resumo


Deciding if a graph is Δ-edge-colourable (resp. (Δ + 1)-total colourable), although it is an NP-complete problem for graphs in general, is polynomially solvable for interval graphs of odd (resp. even) maximum degree Δ. An interesting superclass of the proper interval graphs are the proper circular-arc graphs, for which we suspect that Δ-edge-colourability is linear-time decidable. This work presents sufficient conditions for Δ-edge-colourability, (Δ + 1)-total colourability, and (Δ+2)-total colourability of proper circular-arc graphs. Our proofs are constructive and yield polynomial-time algorithms.

Publicado
26/07/2018
Como Citar

Selecione um Formato
BERNARDI, João Pedro W.; DE ALMEIDA, Sheila M.; ZATESKO, Leandro M.. On Total and Edge-colouring of Proper Circular-arc Graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3557.