Totally critical even order graphs (Q1306315): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1999.1902 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2021132233 / rank | |||
Normal rank |
Revision as of 20:58, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Totally critical even order graphs |
scientific article |
Statements
Totally critical even order graphs (English)
0 references
20 December 1999
0 references
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.
0 references
total chromatic number
0 references
maximum degree
0 references
deficiency
0 references
vertex-coloring
0 references
conformability
0 references
edge independence number
0 references