Hamiltonian colorings of graphs (Q1763479): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q582576 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Stanlislav Jendroľ / rank | |||
Normal rank |
Revision as of 11:50, 16 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonian colorings of graphs |
scientific article |
Statements
Hamiltonian colorings of graphs (English)
0 references
22 February 2005
0 references
A new chromatic parameter of graphs, the Hamiltonian chromatic number, is introduced in this paper. For vertices \(u\) and \(v\) in a connected graph \(G\) of order \(n\), the length of a longest \(u\)-\(v\) path in \(G\) is denoted by \(D(u,v)\). A Hamiltonian coloring \(c\) of \(G\) is an assignment \(c\) of colors (positive integers) to the vertices of \(G\) such that \(D(u,v)+| c(u)-c(v)| \geq n-1\) for every two distinct vertices \(u\) and \(v\) of \(G\). The value \(\text{hc}(c)\) of a Hamiltonian coloring \(c\) of \(G\) is the maximum color assigned to a vertex of \(G\). The Hamiltonian chromatic number \(\text{hc}(G)\) of \(G\) is \(\min\{\text{hc}(c)\}\) over all Hamiltonian colorings \(c\) of \(G\). This parameter is determined for complete graphs \(K_n\), the complete bipartite graphs \(K_{r,s}\) and for the cycle \(C_n\) as follows: \(\text{hc}(K_n)=1\), \(\text{hc}(K_{1,n-1})=(n-2)^2+1\) for \(n\geq2\), \(\text{hc}(K_{r,r})=r\) for \(r\geq2\), \(\text{hc}(K_{r,1})= (s-1)^2+(r-1)^2\) for \(2\leq r<s\), and \(\text{hc}(C_n)=n-2\). The following two general results are proved as well: (1) For every two integers \(k\) and \(n\) with \(k\geq1\) and \(n\geq3\), there exists a Hamiltonian graph of order \(n\) with Hamiltonian chromatic number \(k\) if and only if \(1\leq k\leq n-2\). (2) If \(G\) is a nontrivial connected graph of order \(n\), then \(\text{hc}(G)\leq(n-2)^2+1\).
0 references
Hamiltonian coloring
0 references
Hamiltonian-connected graphs
0 references
Radio coloring
0 references