Totally critical even order graphs

DOI10.1006/JCTB.1999.1902MaRDI QIDQ1306315zbMATH OpenOpenAlexFDO

Authors G. M. Hamilton, H. R. F. Hind, A. J. W. Hilton

Publication date 20 December 1999

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1999.1902

zbMATH Keywords

conformability deficiency edge independence number maximum degree total chromatic number vertex-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Review text

A connected graph \(G\) is totally critical if its total chromatic number is at least two more than its maximum degree and is reduced by the removal of an arbitrary edge. Let \(G(p,q)\) have maximum degree \(\Delta(G)\); the deficiency of \(G\) is given by \(\text{def}(G)= \Delta(G)p- 2q\). A vertex-coloring of \(G\) from color set \(\{1,2,\dots, \Delta+1\}\) is conformable if the number of color classes (including empty ones) whose parity differs from that of \(p\) is at most \(\text{def}(G)\); \(G\) is conformable if it has such a vertex-coloring. The conformability conjecture is: Let \(G\) satisfy \(\Delta(G)\geq (p+1)/2\); then \(G\) is totally critical if and only if \(G\) is non-conformable and has no non-conformable subgraphs of the same maximum degree, or \(\Delta(G)\) is even and \(G\) results from the complete graph of order \(\Delta(G)+1\) by subdividing one edge. The authors show that if this conjecture is true, then totally critical even-order graphs with maximum degree at least half their order are characterized by a simple equation involving the order, maximum degree, and deficiency of the graph and the edge independence number of the complement.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Totally critical even order graphs

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