On edge-colouring indifference graphs

DOI10.1016/S0304-3975(96)00264-2zbMath0901.68148MaRDI QIDQ1391299

João Meidanis, Célia Picinin de Mello, Celina M. Herrera de Figueiredo

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

indifference graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

The chromatic index of proper circular-arc graphs of odd maximum degree which are chordal ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Decompositions for the edge colouring of reduced indifference graphs. ⋮ The total chromatic number of split-indifference graphs ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory

Cites Work

• A linear-time algorithm for proper interval graph recognition
• The chromatic index of graphs with large maximum degree
• Two conjectures on edge-colouring
• NP-completeness of edge-colouring some restricted graphs
• Characterizing and edge-colouring split-indifference graphs
• On the compatibility between a graph and a simple order
• The chromatic index of graphs with a spanning star
• The NP-Completeness of Edge-Coloring
• Odd Minimum Cut-Sets and b-Matchings
• The chromatic index of complete multipartite graphs
• Unnamed Item

This page was built for publication: On edge-colouring indifference graphs