Hamiltonian colorings of graphs (Q1763479): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.dam.2004.08.007 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2061630761 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2765170 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4665539 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2718341 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Radio antipodal colorings of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Radio k-colorings of paths / rank | |||
Normal rank |
Latest revision as of 18:24, 7 June 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