Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs

DOI10.1016/j.dam.2023.11.031zbMath1530.05039OpenAlexW4389121146MaRDI QIDQ6145813

Sheila Morais de Almeida, Cintia Izabel Cararo, Cândida Nunes da Silva

Publication date: 9 January 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2023.11.031

zbMATH Keywords

split graphLatin squarechromatic indexclassification problemedge-coloring problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-completeness of edge-colouring some restricted graphs
• Edge coloring regular graphs of high degree
• Revising Johnson's table for the 21st century
• The NP-completeness column: an ongoing guide
• Graphs which are vertex-critical with respect to the edge-chromatic number
• The chromatic index of graphs with a spanning star
• The NP-Completeness of Edge-Coloring
• The chromatic index of graphs of even order with many edges
• Edge coloring graphs with large minimum degree

This page was built for publication: Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs