Coloring edges of self-complementary graphs

DOI10.1016/S0166-218X(97)00049-8MaRDI QIDQ1373172zbMATH OpenOpenAlexFDO

Authors Małgorzata Zwonek, Adam Paweł Wojda

Publication date 6 May 1998

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

chromatic indexself-complementary graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

According to the well-known Vizing theorem a graph \(G\) is said to be Class 1 (Class 2) if the chromatic index of \(G\) equals \(h (h+1)\), where \(h\) is the maximum vertex degree of \(G\). The authors show: (i) if a self-complementary graph \(G\) has a complementing permutation that is a cycle, then \(G\) is Class 1, and (ii) every regular self-complementary graph is Class 2. The authors conjecture that a self-complementary graph is Class 2 iff it is regular.

Recommendations

• A note on the colour class of a self-complementary graph
• scientific article; zbMATH DE number 3873358
• Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree
• scientific article; zbMATH DE number 3875312

Cites work

• scientific article; zbMATH DE number 49665 (Why is no real title available?)
• scientific article; zbMATH DE number 3194323 (Why is no real title available?)
• Matching theory
• Selbstkomplementäre Graphen
• The NP-Completeness of Edge-Coloring

Cited in

(4)

• A note on the colour class of a self-complementary graph
• Edge colored complete graphs and a generalization of self-complementarity
• scientific article; zbMATH DE number 7663615 (Why is no real title available?)
• On the chromatic index of complementary prisms

This page was built for publication: Coloring edges of self-complementary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1373172)