Total chromatic number of one kind of join graphs

DOI10.1016/J.DISC.2006.03.056MaRDI QIDQ2501562zbMATH OpenOpenAlexFDO

Authors Guangrong Li, Limin Zhang

Publication date 14 September 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.03.056

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

A total \(k\)-coloring of a graph \(G=(V,E)\) is an assigment of \(k\) colors to the elements of \(V\cup E\) such that incident elements receive different colors. The total chromatic number \(\chi_T(G)\) of \(G\) is the smallest integer \(k\) for which \(G\) admits a total \(k\)-coloring. The join of two (disjoint) graphs \(G\) and \(H\) is obtained from \(G\cup H\) by adding new edges \(xy\) between all vertices \(x\) in \(G\) and an \(y\) in \(H\). The authors prove that \(\chi_T(G) =\Delta(G) + 1\) whenever \(G\) is the join of a complete bipartite graph and a path (\(\Delta(G)\) denotes the maximum vertex degree in \(G\)).

Recommendations

• scientific article; zbMATH DE number 979983
• scientific article; zbMATH DE number 1998288
• scientific article; zbMATH DE number 1159270
• Total colorings of some join graphs
• On the total coloring of the join graph of a fan and a complete balanced bipartite graph

Cites work

• A total-chromatic number analogue of Plantholt's theorem
• Graph theory
• scientific article; zbMATH DE number 3943825 (Why is no real title available?)
• scientific article; zbMATH DE number 867691 (Why is no real title available?)
• scientific article; zbMATH DE number 3428958 (Why is no real title available?)
• The Colour Numbers of Complete Graphs

Cited in

(18)

• Equitable total coloring of C_m C_n
• Total chromatic numbers
• Generalization of two results of Hilton on total-colourings of a graph
• The locating chromatic number of the join of graphs
• Total colorings of some join graphs
• Total chromatic number of \{square,unichord\}-free graphs
• A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs
• On the total coloring of the join graph of a fan and a complete balanced bipartite graph
• Edge-colouring and total-colouring chordless graphs
• (2,1)-total number of joins of paths and cycles
• scientific article; zbMATH DE number 978021 (Why is no real title available?)
• scientific article; zbMATH DE number 979983 (Why is no real title available?)
• scientific article; zbMATH DE number 1998288 (Why is no real title available?)
• Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
• Total chromatic number of honeycomb network
• Total colorings-a survey
• Total chromatic number of unichord-free graphs
• Total coloring of some graph operations

This page was built for publication: Total chromatic number of one kind of join graphs

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